求某个区间的最大(小)值，可以使用单调队列
单调栈的作用：存放之前遍历过的元素i，当比nums[i]更大(小)的元素出现时，计算结果，并将i弹出
维护一个单调递减的双端队列，队列大小为[0, k]，队列存储数组下标，从而更好判断滑动窗口区间
存储答案的队列res大小为n - k + 1
遍历数组nums
当队列不为空且当前元素大于队尾元素在nums中对应的值时，将队尾元素弹出，从而保持队列的单调递减性
1
2
| while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()])
queue.pollLast();
|
完成步骤4后，将当前元素nums[i]加入队列
当队首元素等于i - k，说明已经遍历过k轮，滑动窗口的左边界已经超过队首元素了，弹出队首元素
1
2
| if (queue.peekFirst() == i - k)
queue.pollFirst();
|
只有当i >= k - 1时，才记录结果res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> queue = new LinkedList();
for (int i = 0; i < n; ++i) {
while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()])
queue.pollLast();
queue.offerLast(i);
if (queue.peekFirst() == i - k)
queue.pollFirst();
if (i >= k - 1)
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
|
单调栈是一种基于栈的数据结构，所谓的单调就是满足单调递增（单调递减）的栈。主要用于解决 下一个更大的元素问题，也就是找到下一个更大的元素。
单调栈的意义：用 O(n) 复杂度的一重遍历找到每个元素前后最近的更小/大元素位置
方法一：单调栈
- 创建一个栈，存储元素下标
- 遍历数组元素
- 当栈不为空且数组元素值 > 栈顶元素对应数组的值
- 弹出栈顶元素并用变量i - topIndex;接收
- topIndex的下一个更大值的距离为i - topIndex;
- 将i压栈
遍历完for循环，如果栈不为空，说明栈里的元素不存在比它更大的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int topIndex = stack.pop();
res[topIndex] = i - topIndex;
}
stack.push(i);
}
return res;
}
}
|
方法一：单调栈 + HashMap
res[i] = map.getOrDefault(nums1[i], -1);假设nums1[i]在nums2中的下标为j，如果map查不到nums1[i]，说明nums2[j]在j之后没有比nums2[j]更大的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack = new Stack<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums2.length; ++i) {
while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
int topIndex = stack.pop();
map.put(nums2[topIndex], nums2[i]);
}
stack.push(i);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; ++i) {
res[i] = map.getOrDefault(nums1[i], -1);
}
return res;
}
}
|
方法一：单调栈
- 初始res数组为-1很重要！默认所有元素都没有更大的下一个元素
- 循环数组遍历两次，即使第一轮遍历已经被赋值，第二轮也只会赋相同的值，不影响
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
Stack<Integer> stack = new Stack<>();
int[] res = new int[n];
Arrays.fill(res, -1);
for (int i = 0; i < 2 * n; ++i) {
while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
int topIndex = stack.pop();
res[topIndex] = nums[i % n];
}
stack.push(i % n);
}
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
| class Solution {
public String removeDuplicateLetters(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i)
++count[s.charAt(i) - 'a'];
boolean[] visited = new boolean[26];
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
--count[ch - 'a'];
if (visited[ch - 'a'])
continue;
while(!stack.isEmpty() && s.charAt(stack.peek()) > ch && count[s.charAt(stack.peek()) - 'a'] > 0) {
visited[s.charAt(stack.peek()) - 'a'] = false;
stack.pop();
}
visited[ch - 'a'] = true;
stack.push(i);
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty())
sb.append(s.charAt(stack.pollLast()));
return sb.toString();
}
}
|
方法一：单调栈
思路
- 对于一个高度，如果能得到向左和向右的边界
- 那么就能对每个高度求一次面积
- 遍历所有高度，即可得出最大面积
- 使用单调栈，在出栈操作时得到前后边界并计算面积
注意边界问题
1
2
| Arrays.fill(rights, n);
Arrays.fill(left, -1);
|
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
30
| class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] rights = new int[n];
Arrays.fill(rights, n);
Deque<Integer> stack = new LinkedList();
for (int i = 0 ; i < n ; i++){
while (!stack.isEmpty() && heights[stack.getLast()] > heights[i]) {
int top = stack.pollLast();
rights[top] = i;
}
stack.addLast(i);
}
int[] left = new int[n];
Arrays.fill(left, -1);
stack.clear();
for (int i = n - 1 ; i >= 0 ; i--) {
while (!stack.isEmpty() && heights[stack.getLast()] > heights[i]) {
int top = stack.pollLast();
left[top] = i;
}
stack.addLast(i);
}
int res = 0;
for (int i = 0 ; i < n ; i++) {
res = Math.max(res, (rights[i] - left[i] - 1) * heights[i]);
}
return res;
}
}
|
方法一：单调栈
优质题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int trap(int[] height) {
int n = height.length, index = 0, res = 0;
Stack<Integer> stack = new Stack<>();
while (index < n) {
while (!stack.isEmpty() && height[index] > height[stack.peek()]) {
int topIndex = stack.pop();
int h = height[topIndex];
if (stack.isEmpty())
break;
int min = Math.min(height[index], height[stack.peek()]);
int width = index - stack.peek() - 1;
res += (min - h) * width;
}
stack.push(index++);
}
return res;
}
}
|
方法一：双栈模拟
创建两个栈：1.ns(num stack)存放数字，2.is(index stack)存放StringBuilder的下标，下面会详细解释两个栈的用法。
遍历字符串s的每个字符ch，有四种情况：
数字：压入数字栈ns中
字符：放入StringBuilder中
左括号[：将StringBuilder的长度压入下标栈is中
右括号]：将数字，也就是重复次数从数字栈ns中取出来，记作t。从下标栈is中取出要复制子串的初始位置index，
将子串sb.substring(index, sb.toString())复制t - 1次(stringbuilder中已经有一份数据了，所以是t-1)
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
30
31
32
33
34
35
| class Solution {
public String decodeString(String s) {
int n = s.length();
Stack<Integer> ns = new Stack<>(), is = new Stack<>();
StringBuilder sb = new StringBuilder();
boolean preIsNum = false;
for (int i = 0; i < n; ++i) {
char ch = s.charAt(i);
if (ch - '0' >= 0 && ch - '0' <= 9) {
if (preIsNum) {
int pre = ns.pop();
ns.push(pre * 10 + ch - '0');
}
else
ns.push(ch - '0');
preIsNum = true;
}
else {
preIsNum = false;
if (ch == '[')
is.add(sb.length());
else if (ch == ']') {
int index = is.pop(), t = ns.pop();
String temp = sb.substring(index, sb.length());
for (int j = 0; j < t - 1; ++j) {
sb.append(temp);
}
}
else
sb.append(ch);
}
}
return sb.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
| class StockSpanner {
Stack<Integer> stack;
List<Integer> nums, count;
public StockSpanner() {
stack = new Stack();
nums = new ArrayList();
count = new ArrayList();
}
public int next(int price) {
int cnt = 1;
while (!stack.isEmpty() && price >= nums.get(stack.peek()))
cnt += count.get(stack.pop());
nums.add(price);
count.add(cnt);
stack.push(nums.size() - 1);
return cnt;
}
}
|