单调栈
# 84. 柱状图中最大的矩形 (opens new window)
class Solution {
int[] heights;
public int largestRectangleArea(int[] heights) {
this.heights = heights;
int ret = 0;
Stack<Integer> stack = new Stack<>();
stack.add(-1);
for(int i=0;i<=heights.length;i++){
while(getHeight(i)<getHeight(stack.peek())){
int x = stack.pop();
ret = Math.max(ret,getHeight(x)*(i-stack.peek()-1));
}
stack.add(i);
}
return ret;
}
int getHeight(int i){
if(i==-1)
return -1;
else if(i==heights.length)
return -1;
else
return heights[i];
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 496. 下一个更大元素 I (opens new window)
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] greater = findGreater(nums2);
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums2.length;i++){
map.put(nums2[i],greater[i]);
}
int[] res = new int[nums1.length];
for(int i=0;i<nums1.length;i++){
res[i] = map.get(nums1[i]);
}
return res;
}
// 寻找数组后面更大元素的下标
int[] findGreater(int[] nums){
int n = nums.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=n-1;i>=0;i--){
while(!stack.isEmpty() && stack.peek()<=nums[i]){
stack.pop();
}
res[i] = stack.isEmpty()?-1:stack.peek();
stack.push(nums[i]);
}
return res;
}
}
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
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 503. 下一个更大元素 II (opens new window)
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=2*n-1;i>=0;i--){
while(!stack.isEmpty() && stack.peek()<=nums[i%n]){
stack.pop();
}
res[i%n] = stack.isEmpty()?-1:stack.peek();
stack.push(nums[i%n]);
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 739. 每日温度 (opens new window)
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=n-1;i>=0;i--){
while(!stack.isEmpty() && temperatures[i]>=temperatures[stack.peek()]){
stack.pop();
}
res[i] = stack.isEmpty()?0:(stack.peek()-i);
stack.push(i);
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 316. 去除重复字母 (opens new window)
1.去重
用一个bool数组记录栈中元素
2.字符串顺序不打乱
栈保证顺序
3.字典序最小
cnt数组，如果后面还有元素可以pop，没有就不能pop
class Solution {
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
int[] cnt = new int[256]; // 记录字符串中字符的数量
for(int i=0;i<s.length();i++){
cnt[s.charAt(i)]++;
}
boolean[] inStack = new boolean[256]; // 栈中不存在重复元素
for(char c:s.toCharArray()){
cnt[c]--;
if(inStack[c])
continue ;
while(!stack.isEmpty() && stack.peek()>c){
// 若之后没有栈顶元素，不要POP
if(cnt[stack.peek()]==0)
break;
// 还有可以pop，为了最小字典序
inStack[stack.pop()] = false;
}
stack.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
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
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29