力扣11
https://leetcode-cn.com/problems/container-with-most-water/
单调栈
860ms
问题在于左边不只是一个栈的问题，而是单增的，比如121，最右的1要和左边的1和2都要比，否则不知道，因此右边递减，左边递增，这种情况是不适合用单调栈的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public int maxArea(int[] height) {
if (height.length < 2) return 0;
int res = 0;
List<Integer> leftList = new ArrayList<>();
Deque<Integer> stack = new LinkedList<>();
stack.offerLast(0);
leftList.add(0);
for (int i = 1; i < height.length; i++) {
if (height[i] > height[leftList.get(leftList.size() - 1)]) leftList.add(i);
while (!stack.isEmpty() && height[i] >= height[stack.peekLast()]){
stack.pollLast();
}
stack.offerLast(i);
}
while (!stack.isEmpty()){
Integer right = stack.pollLast();
for (Integer left : leftList) {
if (left > right) break;
int minHeight = Math.min(height[right], height[left]);
res = Math.max(res, minHeight * (right - left));
}
}
return res;
}
|
双指针
4ms
1
2
3
4
5
6
7
8
9
10
11
| public int maxArea_other(int[] height) {
if(height.length <= 1) return -1;
int i = 0, j = height.length - 1, res = 0;
while(i < j){
int h = Math.min(height[i], height[j]);
res = Math.max(res, h * (j - i));
if(height[i] < height[j]) ++i;
else --j;
}
return res;
}
|
其他双指针类型的题目点击这里