-
从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2] 输出：[2,3,1]分析：可以首先遍历一次链表，获得链表的长度，创建一个相同长度的数组，然后再从头到尾遍历一次，从数组的尾部开始添加元素。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int[] reversePrint(ListNode head) { //先获取链表长度，创建对应长度数组 ListNode currNode = head; int len = 0; while(currNode != null){ len ++; currNode = currNode.next; } int[] result = new int[len]; //再次遍历链表，将值倒序填充至结果数组 currNode = head; while(currNode != null){ result[len - 1] = currNode.val; len --; currNode = currNode.next; } return result; } } -
二维数组的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
分析：这个二维数组有一个特点，右上角的元素是这行中最大的，是这列中最小的，这种类似二叉树。
class Solution {
public static boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int rows = matrix.length;
int columns = matrix[0].length;
int row = 0;
int column = columns - 1;
if(target<matrix[0][0] || target > matrix[rows-1][column]){
return false;
}
while (row<=rows-1 && column >=0){
//如果相等，直接返回true
if(target == matrix[row][column]){
return true;
}
//如果小于当前元素，列数减一
else if(target<matrix[row][column]){
column--;
}
//如果大于当前元素，行数加一
else {
row++;
}
}
return false;
}
}
-
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：3 / \ 9 20 / \ 15 7分析：只要知道一个二叉树的中序遍历结果以及先序遍历和后序遍历中的一个，就能完整地构建出这棵二叉树。
比如一棵二叉树的先序遍历结果为a b c d e f g h j i ，中序遍历的结果为c b e d a h g i j f
我们知道先序遍历的第一个元素必定是根节点，所以根节点是a，从中序遍历的结果中找到a，那么a之前的所有元素都是a的左子树，有4个元素：c b e d，先序遍历中选择4个元素：b c d e。那么b是a的左子树的根节点......在a之后的所有元素都是a的右子树
使用一个 Map 存储中序遍历的每个元素及其对应的下标，目的是为了快速获得一个元素在中序遍历中的位置。调用递归方法，对于前序遍历和中序遍历，下标范围都是从 0 到 n-1，其中 n 是二叉树节点个数。
递归方法的基准情形有两个：判断前序遍历的下标范围的开始和结束，若开始大于结束，则当前的二叉树中没有节点，返回空值 null。若开始等于结束，则当前的二叉树中恰好有一个节点，根据节点值创建该节点作为根节点并返回。
若开始小于结束，则当前的二叉树中有多个节点。在中序遍历中得到根节点的位置，从而得到左子树和右子树各自的下标范围和节点数量，知道节点数量后，在前序遍历中即可得到左子树和右子树各自的下标范围，然后递归重建左子树和右子树，并将左右子树的根节点分别作为当前根节点的左右子节点。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //保存中序遍历的结果集 HashMap<Integer, Integer> dic = new HashMap<>(); //保存先序遍历数组 int[] po; public TreeNode buildTree(int[] preorder, int[] inorder) { po = preorder; //遍历中序结果集放进HashMap中方便查询获得根节点 for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } /** * pre_root是先序遍历结果集中的根节点 * in_left是中序遍历的左边界 * in_right是中序遍历的右边界 */ TreeNode recur(int pre_root, int in_left, int in_right) { //如果左边界大于右边界，停止递归 if(in_left > in_right) return null; //生成一个根节点 TreeNode root = new TreeNode(po[pre_root]); //找到这个根节点在中序遍历集中的位置 int i = dic.get(po[pre_root]); //左子树 root.left = recur(pre_root + 1, in_left, i - 1); //右子树，根节点索引+左子树长度+1 root.right = recur(pre_root + i - in_left + 1, i + 1, in_right); return root; } } -
最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
public static int lengthOfLongestSubstring(String s){
//这里 是不包含start的
//ans是最大子串的长度，初始为0，start是最大子串的开始的下标的前一位，初始为-1
int ans = 0, start = -1;
//使用Map存储字符及对应的下标
Map<Character, Integer> map = new HashMap<>();
//遍历这个字符串
for(int i = 0; i < s.length() ; i++){
char k = s.charAt(i);
if(map.containsKey(k)){
// 如果遇到重复字符，就要更新了！
int index = map.get(k);
//index是当前重复字符对应的下标，如果大于start
if(index > start) {
start = index;
}
}
map.put(k, i);
//比较
ans = Math.max(ans, i - start);
}
return ans;
}
-
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]解法一：暴力破解法
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[] { i, j }; } } } throw new IllegalArgumentException("No two sum solution"); } }暴力破解法的时间复杂度是O(n^2)，空间复杂度是O(1).
解法二：哈希表的一次遍历
class Solution{ public int[] twoSum(int[] nums, int target){ Map<Integer,Integer> map = new HashMap<>(); for(int i = 0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ return new int[]{map.get(target-nums[i]),i}; } map.put(nums[i],i); } throw new IllegalArgumentException("No two sum solution"); } }这种方法的时间复杂度是O(n)，空间复杂度也是O(n)。
-
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807分析：最开始想的是分别将这两个链表转换为int型的整数，然后两数相加得到一个int整数，最后将这个整数转成链表。可惜这个想法太天真了，不仅时间复杂度很高，而且还会出现int溢出的问题。最后看了答案：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1,q = l2,curr = dummyHead; int carry = 0; while (p != null || q!= null){ int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = x + y + carry; carry = sum / 10; curr.next = new ListNode(sum%10); curr = curr.next; if(p != null){ p = p.next; } if( q != null){ q = q.next; } } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; }使用了一个dummyHead作为头节点之前的节点。0-9之内的数字相加有可能出现溢出的问题使用carry保存溢出的十位上的数字。最后还有可能出现进位的问题，所以要对carry进行判断。
-
寻找两个正序数组的中位数(https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/)
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
分析：刚开始的时候我的思路是将这两个数组合并为一个大数组，然后根据合并后数组的长度计算中位数。但是这种算法的时间复杂度为O(m+n)，不能满足题目的要求。无奈只能看参考答案：
public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int leftLength = nums1.length; int rightLength = nums2.length; // 为了保证第一个数组比第二个数组小(或者相等) if (leftLength > rightLength) { return findMedianSortedArrays(nums2, nums1); } // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2; // 两个数组长度之和为偶数时，当在长度之和上+1时，由于整除是向下取整，所以不会改变结果 // 两个数组长度之和为奇数时，按照分割线的左边比右边多一个元素的要求，此时在长度之和上+1，就会被2整除，会在原来的数 //的基础上+1，于是多出来的那个1就是左边比右边多出来的一个元素 int totalLeft = (leftLength + rightLength + 1) / 2; // 在 nums1 的区间 [0, leftLength] 里查找恰当的分割线， // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i] int left = 0; int right = leftLength; // nums1[i - 1] <= nums2[j] // 此处要求第一个数组中分割线的左边的值 不大于(小于等于) 第二个数组中分割线的右边的值 // nums2[j - 1] <= nums1[i] // 此处要求第二个数组中分割线的左边的值 不大于(小于等于) 第一个数组中分割线的右边的值 // 循环条件结束的条件为指针重合，即分割线已找到 while (left < right) { // 二分查找，此处为取第一个数组中左右指针下标的中位数，决定起始位置 // 此处+1首先是为了不出现死循环，即left永远小于right的情况 // left和right最小差距是1，此时下面的计算结果如果不加1会出现i一直=left的情况，而+1之后i才会=right // 于是在left=i的时候可以破坏循环条件，其次下标+1还会保证下标不会越界，因为+1之后向上取整，保证了 // i不会取到0值，即i-1不会小于0 // 此时i也代表着在一个数组中左边的元素的个数 int i = left + (right - left + 1) / 2; // 第一个数组中左边的元素个数确定后，用左边元素的总和-第一个数组中元素的总和=第二个元素中左边的元素的总和 // 此时j就是第二个元素中左边的元素的个数 int j = totalLeft - i; // 此处用了nums1[i - 1] <= nums2[j]的取反，当第一个数组中分割线的左边的值大于第二个数组中分割线的右边的值 // 说明又指针应该左移，即-1 if (nums1[i - 1] > nums2[j]) { // 下一轮搜索的区间 [left, i - 1] right = i - 1; // 此时说明条件满足，应当将左指针右移到i的位置，至于为什么是右移，请看i的定义 } else { // 下一轮搜索的区间 [i, right] left = i; } } // 退出循环时left一定等于right，所以此时等于left和right都可以 // 为什么left一定不会大于right?因为left=i。 // 此时i代表分割线在第一个数组中所在的位置 // nums1[i]为第一个数组中分割线右边的第一个值 // nums[i-1]即第一个数组中分割线左边的第一个值 int i = left; // 此时j代表分割线在第二个数组中的位置 // nums2[j]为第一个数组中分割线右边的第一个值 // nums2[j-1]即第一个数组中分割线左边的第一个值 int j = totalLeft - i; // 当i=0时，说明第一个数组分割线左边没有值，为了不影响 // nums1[i - 1] <= nums2[j] 和 Math.max(nums1LeftMax, nums2LeftMax) // 的判断，所以将它设置为int的最小值 int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1]; // 等i=第一个数组的长度时，说明第一个数组分割线右边没有值，为了不影响 // nums2[j - 1] <= nums1[i] 和 Math.min(nums1RightMin, nums2RightMin) // 的判断，所以将它设置为int的最大值 int nums1RightMin = i == leftLength ? Integer.MAX_VALUE : nums1[i]; // 当j=0时，说明第二个数组分割线左边没有值，为了不影响 // nums2[j - 1] <= nums1[i] 和 Math.max(nums1LeftMax, nums2LeftMax) // 的判断，所以将它设置为int的最小值 int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1]; // 等j=第二个数组的长度时，说明第二个数组分割线右边没有值，为了不影响 // nums1[i - 1] <= nums2[j] 和 Math.min(nums1RightMin, nums2RightMin) // 的判断，所以将它设置为int的最大值 int nums2RightMin = j == rightLength ? Integer.MAX_VALUE : nums2[j]; // 如果两个数组的长度之和为奇数，直接返回两个数组在分割线左边的最大值即可 if (((leftLength + rightLength) % 2) == 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { // 如果两个数组的长度之和为偶数，返回的是两个数组在左边的最大值和两个数组在右边的最小值的和的二分之一 // 此处不能被向下取整，所以要强制转换为double类型 return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2; } }这种方式基于一种分割线的思路来寻找中位数。第一个数组有一个分割线，第二个数组也有一个分割线，分割线左侧的所有元素要小于分割线右侧的所有元素，也就意味着第一个数组的分割线左侧的最后一个元素要小于第二个数组分割线右侧的第一个元素，同理，第二个数组的分割线左侧的最后一个元素要小于第一个数组分割线右侧的第一个元素。同时，上下两个数组分割线左侧的元素的数量是(上面数组的元素个数+下面数组的元素的个数+1)/2。当总元素的个数是偶数的时候，左侧的元素的数量是总元素数量的一半，当是奇数的时候，左侧元素的数量是总元素的数量的一半再加一。这种思路相当于只要找到上下两个数组的分割线两侧的四个元素就可以计算出中位数了。
需要注意的是有四种特殊情况：上面的数组分割线左边没有元素、右边没有元素，下面的数组分割线左边没有元素，右边没有元素。
-
最长回文子串
给定一个字符串
s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。示例 2：
输入: "cbbd" 输出: "bb"
解法一：中心扩展算法
对每一个字符，向两边扩展，可以分为两种情况：奇数与偶数，分别计算这两种情况下最长回文子串的值并进行比较。
/**
* 中心扩散法寻找最长子串
* @param s
* @return
*/
public String longestPalindrome(String s) {
if (s == null || s.length() < 1){
return "";
}
// 初始化最大回文子串的起点和终点
int start = 0;
int end = 0;
// 遍历每个位置，当做中心位
for (int i = 0; i < s.length(); i++) {
// 分别拿到奇数偶数的回文子串长度
int lenOdd = expandCenter(s,i,i);
int lenEven = expandCenter(s,i,i + 1);
// 对比最大的长度
int len = Math.max(lenOdd,lenEven);
// 计算对应最大回文子串的起点和终点
//与len>=end-start+1同样的效果
if (len > end - start){
//len-1兼顾了偶数的情况
start = i - (len - 1)/2;
end = i + len/2;
}
}
// 注意：这里的end+1是因为 java自带的左闭右开的原因
return s.substring(start,end + 1);
}
/**
*
* @param s 输入的字符串
* @param left 起始的左边界
* @param right 起始的右边界
* @return 回文串的长度
*/
private int expandCenter(String s,int left,int right){
// left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
// right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
// 跳出循环的时候恰好满足 s.charAt(left) ！= s.charAt(right)
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
// 回文串的长度是right-left+1-2 = right - left - 1
return right - left - 1;
}
解法二：动态规划
使用一个二维数组表示各个阶段的状态，这个二维数组的行是子串的起始位置，列是子串的结束位置。由于j>=i，所以只需要考虑二维数组的主对角线的上半部分，对角线上的值永远是true。用true表示这个子串是回文串，false不是回文串。那么对于某个固定位置的数组元素来说，它的值依赖于左下角的元素的值。进行填充的时候只能一列一列地进行填充，同一列的元素从上到下依次填充。
给定一个字符串s="abcba"
0 1 2 3 4 0 true false false false true 1 true false true false 2 true false false 3 true false 4 true
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
// 特判
if (len < 2){
return s;
}
//最大长度初始是1
int maxLen = 1;
int begin = 0;
// 1. 状态定义
// dp[i][j] 表示s[i...j] 是否是回文串
// 2. 初始化
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] chars = s.toCharArray();
// 3. 状态转移
// 注意：先填左下角
// 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算
for (int j = 1;j < len;j++){
for (int i = 0; i < j; i++) {
// 头尾字符不相等，不是回文串
if (chars[i] != chars[j]){
dp[i][j] = false;
}else {
// 相等的情况下
// 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
if (j - i < 3){
dp[i][j] = true;
}
//否则，判断其左下角的元素的状态
else {
// 状态转移
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
// 此时更新记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
// 4. 返回值
return s.substring(begin,begin + maxLen);
}
}
-
Z字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R E T O E S I I G E D H N之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
分析：最后需要按行读取，所以可以考虑每一行使用一个字符串进行保存。最后将字符串进行拼接。最开始的想法是用一个变量记录当前所在的行，但是有一个问题，行数加一还是减一怎么判断，苦思冥想不了了之，看了官方题解才恍然大悟，使用一个标志位进行标记。根据这个标志位的状态进行加一或是减一的操作。
public static String convert(String s, int numRows){ //如果行数为1或者字符串的长度小于等于行数，就返回字符串本身，不需要转换 if(numRows == 1 || s.length()<=numRows){ return s; } //同一行的字符保存在一个StringBuilder中，需要一个list来存放这些StringBuilder List<StringBuilder> list = new ArrayList<>(); char[] chars = s.toCharArray(); for (int i = 0; i < numRows; i++) { list.add(new StringBuilder()); } //状态位，根据这个变量判断行数加一还是减一 boolean goingDown = false; //初始当前行为1 int curRow = 1; //遍历每个字符，追加到对应的StringBuilder后面 for (char aChar : chars) { //因为list的下标从0开始，所以curRow需要减一 list.get(curRow-1).append(aChar); //如果是第一行或者最后一行就需要对goingDown进行取反操作 if (curRow == 1 || curRow == numRows) { goingDown = !goingDown; } //根据goingDown的值进行加一或者减一的操作 curRow += goingDown ? 1 : -1; } StringBuilder sb = new StringBuilder(); //合并list中的stringBuilder for (StringBuilder builder : list) { sb.append(builder); } return sb.toString(); }- 正则表达式匹配(难度：困难)
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。示例 2:
输入:
s = "aa"
p = "a"
输出: true
解释: 因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3:
输入:
s = "ab"
p = "."
输出: true
解释: "." 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:输入:
s = "aab"
p = "cab"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:输入:
s = "mississippi"
p = "misisp*."
输出: false
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
}
else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
//.可以匹配任意字符，所以返回true
if (p.charAt(j - 1) == '.') {
return true;
}
//i-1与j-1是否匹配
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
-
盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
> 分析：
>
> 这道一乍一看不就是一个双重for循环吗，很简单的一道题，为什么还是中等难度。结果一提交运行速度只击败了14.7%的用户。寻思这还有其他更快速的算法，苦思冥想有一个双指针的方法，一个指针指向头，一个指针指向尾，循环的终止条件是指针重合。但是在判断应该移动哪个指针的问题上不知道怎么办。果断看了答案，原来只需要移动元素值较小的那个指针就行了。原因就是如果说你移动元素值较大的那个指针，无论下一个元素的值大还是小。面积一定小于之前的面积。所以只能移动较小元素的那个指针，时间复杂度是O(n)。
```java
public static int maxArea(int[] height){
int max = 0;
int length = height.length;
// 双重循环的方法
// for (int i = 0; i < length-1; i++) {
// for (int j = i+1; j < length; j++) {
// int min = Math.min(height[i], height[j]);
// int temp = min*(j-i);
// if(temp>max){
// max = temp;
// }
// }
// }
// return max;
int left = 0;
int right = length-1;
while (left<right){
int min = Math.min(height[left],height[right]);
int temp = min*(right-left);
max = Math.max(temp, max);
if(height[left]<=height[right]){
left++;
}
else {
right--;
}
}
return max;
}
```
网友评论