单调栈 LeetCode
单调栈
单调栈：这题考的基础模型其实就是：在一维数组中对每一个数找到第一个比自己小的元素。
这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。
重要的是：将问题转化成找到下一个 比当前值大/小的 值的下标
package leetcode;
import java.util.*;
public class MonotonousStackDemo {
public static void main(String[] args) {
}
}
/**
* 84. 柱状图中最大的矩形
*/
/*
空间优化
概括的说：矩形高度相等的时候，虽然按照左边柱子来算，答案不对，但是最右边的来算，结果是对的，我们只需要保存一个正确的就可。
等等，我们需要的是「一根柱子的右侧且最近的小于其高度的柱子」，但这里我们求的是小于等于，那么会造成什么影响呢？
答案是：我们确实无法求出正确的右边界，但对最终的答案没有任何影响。
这是因为在答案对应的矩形中，如果有若干个柱子的高度都等于矩形的高度，那么最右侧的那根柱子是可以求出正确的右边界的，
而我们没有对求出左边界的算法进行任何改动，因此最终的答案还是可以从最右侧的与矩形高度相同的柱子求得的。
*/
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
right[stack.pop()] = i;
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int area = (right[i] - left[i] - 1) * heights[i];
ans = Math.max(ans, area);
}
return ans;
}
}
// 先左后右，记住当前柱子左侧和右侧小于其高度的柱子下标
class Solution130 {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
// 忘记清除
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int area = (right[i] - left[i] - 1) * heights[i];
ans = Math.max(ans, area);
}
return ans;
}
}
/**
* 42. 接雨水
*/
// 单调栈，按行计算；前两种方法用的都是按列计算雨水数量
class Solution129 {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<>();
int n = height.length;
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) break;
int left = stack.peek();
int wid = i - left - 1;
int hgh = Math.min(height[left], height[i]) - height[top];
ans += wid * hgh;
}
stack.push(i);
}
return ans;
}
}
// 动态规划
class Solution128 {
public int trap(int[] height) {
int n = height.length;
int[] lMax = new int[n];
int[] rMax = new int[n];
lMax[0] = height[0];
for (int i = 1; i < n; i++) {
lMax[i] = Math.max(lMax[i - 1], height[i]);
}
rMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rMax[i] = Math.max(rMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int count = Math.min(lMax[i], rMax[i]) - height[i];
System.out.println(ans);
if (count > 0) ans += count;
}
System.out.println(Arrays.toString(lMax));
System.out.println(Arrays.toString(rMax));
return ans;
}
}
// 巧妙的双指针
class Solution127 {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
// left < right；相遇的时候，left与right一定为最大值
// left <= right也可以，最大值时计算ans += 0；
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
left++;
} else {
ans += rightMax - height[right];
right--;
}
}
return ans;
}
}
/**
* 503. 下一个更大元素 II
*/
class Solution126 {
public int[] nextGreaterElements(int[] t) {
LinkedList<Integer> stack = new LinkedList<>();
int[] ret = new int[t.length];
Arrays.fill(ret, -1);
for (int i = 0; i < t.length * 2; i++) {
int j = i % t.length;
while (!stack.isEmpty() && t[j] > t[stack.peek()]) {
ret[stack.peek()] = t[j];
stack.pop();
}
stack.push(j);
}
return ret;
}
}
/**
* 496. 下一个更大元素 I
*/
class Solution125 {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] ret = new int[nums1.length];
Arrays.fill(ret, -1);
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
map.put(nums1[i], i);
}
LinkedList<Integer> stack = new LinkedList<>();
stack.push(0);
for (int i = 0; i < nums2.length; i++) {
while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
int val = nums2[stack.peek()];
if (map.containsKey(val)) {
ret[map.get(val)] = nums2[i];
}
stack.pop();
}
stack.push(i);
}
return ret;
}
}
/**
* 739. 每日温度
*/
// 使用LinkedList当做栈比Stack要快很多啊
// Stack底层实现是数组
class Solution124 {
public int[] dailyTemperatures(int[] t) {
LinkedList<Integer> stack = new LinkedList<>();
int[] ret = new int[t.length];
stack.push(0);
for (int i = 1; i < t.length; i++) {
while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
ret[stack.peek()] = i - stack.pop();
}
stack.push(i);
}
return ret;
}
}
class Solution123 {
public int[] dailyTemperatures(int[] t) {
Stack<Integer> stack = new Stack<>();
int[] ret = new int[t.length];
stack.push(0);
for (int i = 1; i < t.length; i++) {
while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
ret[stack.peek()] = i - stack.pop();
}
stack.push(i);
}
return ret;
}
}