单调栈题解
单调栈结构
方法：单调栈
算法
这里维护一个单调递增栈，可以找到比当前元素要小的元
约定：当前元素 cur，栈顶元素 top，出栈的栈顶元素 tempTop
- 遍历数组
- 如果当前元素大于栈顶元素，则入栈(入栈元素索引，而不是值)
- 否则，将栈顶元素出栈，此时，离 tempTop 左边最近且值比 tempTop 小的就是当前的栈顶元素 top，离 tempTop 右边最近且值比 tempTop 小的就是当前元素 cur。 然后循环此过程，直到第二步条件满足。
- 遍历数组结束后，最后将栈内元素按上述规则输出
private static void leftRightWay(int[] arr){
int len = arr.length;
int[] right = new int[len];
int[] left = new int[len];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < len; i++) {
while(!stack.empty() && arr[i] < arr[stack.peek()]) {
int tempTop = stack.pop();
left[tempTop] = stack.empty() ? -1 : stack.peek();
right[tempTop] = i;
}
stack.push(i);
}
while(!stack.empty()) {
int tempTop = stack.pop();
left[tempTop] = stack.empty() ? -1 : stack.peek();
right[tempTop] = -1;
}
for(int i = 0; i < len; i++) {
System.out.println(left[i] + " " + right[i]);
}
}
复杂度
- 时间复杂度：O(N)，每个元素被处理两次，其索引入栈和出栈。
739. 每日温度
方法一：动态规划，详解可去链接里查看
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] result = new int[len];
result[len - 1] = 0;
for(int i = len - 2; i >= 0; i--) {
for(int j = i + 1; j < len; j += result[j]) {
// 重点在 j += result[j] 上
// 当天温度小于后一天温度，那么直接得出结果 1
// 当天温度大于后一天温度，那么就得比较 [比后一天温度还要高的那一天]，循环这个过程。
// 如果后一天温度的后面没有比它大的了，那自然也不可能比当天温度大了
if (T[i] < T[j]) {
result[i] = j - i;
break;
} else if (result[j] == 0) {
result[i] = 0;
break;
}
}
}
return result;
}
方法二：单调栈
算法
维护一个单调递减的栈即可，栈内存放的是元素索引
- 遍历数组
- 如果当前元素小于栈顶元素，则入栈
- 否则，将栈顶元素出栈，
当前元素索引 - 栈顶元素就是对应位置的结果
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] result = new int[len];
Stack<Integer> stack = new Stack();
for(int i = 0; i < len; i++) {
while(!stack.empty() && T[i] > T[stack.peek()]) {
int tempTop = stack.pop();
result[tempTop] = i - tempTop;
}
stack.push(i);
}
while(!stack.empty()) {
result[stack.pop()] = 0;
}
return result;
}
