单调栈专题,用栈来记录一个递增或递减的序列,并在遍历过程中进出栈,维持栈内元素的递增或递减关系(非严格)。一般用来求解当前元素右边第一个比它大/小的元素。
LeetCode 739 每日温度
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
int[] result = new int[temperatures.length];
for (int i = 1; i < temperatures.length; i++) {
if (temperatures[i] > temperatures[stack.peek()]) {
while (stack.size() > 0 && temperatures[i] > temperatures[stack.peek()]) {
result[stack.peek()] = i-stack.peek();
stack.pop();
}
stack.push(i);
} else {
stack.push(i);
}
}
return result;
}
}
本题使用单调栈寻找右边第一个更大元素和当前元素之间的距离,为了方便寻找元素,栈内保存的是下标而非实际的值。
LeetCode 496 下一个更大元素 I
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
int[] result = new int[nums2.length];
for (int i = 0; i < nums2.length; i++) result[i] = -1;
for (int i = 1; i < nums2.length; i++) {
if (nums2[i] > nums2[stack.peek()]) {
while (stack.size() > 0 && nums2[i] > nums2[stack.peek()]) {
result[stack.peek()] = nums2[i];
stack.pop();
}
stack.push(i);
} else {
stack.push(i);
}
}
int res[] = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]) {
res[i] = result[j];
}
}
}
return res;
}
}
本题在上一题基础上有所改进,用两个数组进行了映射操作,难度系数并未有明显增加,但还存在可以改进的空间。
LeetCode 503 下一个更大元素II
class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] result = new int[nums.length];
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
for (int i = 0; i < nums.length; i++) result[i] = -1;
for (int i = 1; i < nums.length * 2; i++) {
if (nums[i%nums.length] > nums[stack.peek()]) {
while (stack.size() > 0 && nums[i%nums.length] > nums[stack.peek()]) {
result[stack.peek()] = nums[i%nums.length];
stack.pop();
}
stack.push(i%nums.length);
} else {
stack.push(i%nums.length);
}
}
return result;
}
}
这题用到了一个小技巧:总长度为数组长度*2,过程中取值时用i%nums.length可得到循环的效果。