经典用法

单调栈问题，就是当你分析问题时，需要你找到一个索引左右两边大于或者小于自己的最近索引时，就使用单调栈！

总结

每日最高温度

leetcode 739

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

思路：将下标一次放入栈，但遵循以下要求，如果当前的温度大于栈顶的温度，则栈顶的索引出栈，并记录当前索引与栈顶索引的差值，即当前索引与栈顶索引的差值就是当前索引对应的天数。循环弹出，直到栈为空或者栈顶的索引对应的温度大于等于当前索引对应的温度。则当前索引入栈。

public static int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    size = 0;
    int[] ans = new int[n];
    for(int i =0;i<n;i++){
        while( size>0 && temperatures[stack[size-1]] < temperatures[i]){
            ans[stack[size-1]] = i - stack[size-1];
            size --;
        }
        stack[size++] = i;
    }
    return ans;
}

子数组的最小值之和

leetcode 907

思路：根据单调栈，可以知道每个索引左边跟右边小于他的最近索引，那么对于每个索引，左边小于它的最近索引为left[i]，右边小于它的最近索引为right[i]，则对于索引i，最小值之和为(right[i] - i) (i - left[i]) arr[i]。（这就是包含了i的且i为最小值的所有子数组的最小值之和）。最后剩在栈里面的它的右边索引就在n的位置。

   public static int sumSubarrayMins(int[] arr) {
	long ans = 0;
	r = 0;
	// 注意课上讲的相等情况的修正
	for (int i = 0; i < arr.length; i++) {
		while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
			int cur = stack[--r];
			int left = r == 0 ? -1 : stack[r - 1];
			ans = (ans + (long) (cur - left) * (i - cur) * arr[cur]) % MOD;
		}
		stack[r++] = i;
	}
	while (r > 0) {
		int cur = stack[--r];
		int left = r == 0 ? -1 : stack[r - 1];
		ans = (ans + (long) (cur - left) * (arr.length - cur) * arr[cur]) % MOD;
	}
	return (int) ans;
}

柱状图中最大矩形

leetcode 84

思路：单调栈，对于每个索引，左边小于它最近索引为left[i]，右边小于它最近索引为right[i]，则对于索引i，最大矩形为(right[i] - left[i] - 1) * heights[i]。这道题就是一个非常标准的单调栈问题。

标准模板

public static int largestRectangleArea(int[] heights) {
    int n =heights.length;
    size = 0;
    int ans = 0;
    for(int i =0;i<n;i++){
        while(size>0 && heights[stack[size-1]] >= heights[i]){
            int temp = stack[--size];
            ansArr[temp][0] = size == 0 ? -1 : stack[size-1];
            ansArr[temp][1] = i;
        }
        stack[size++] = i;
    }
    while(size>0){
        int temp = stack[--size];
        ansArr[temp][0] = size==0? -1 :stack[size-1];
        ansArr[temp][1] = n;
    }
    //修正右边
    for(int i = n-2;i>=0;i--){
        if(ansArr[i][1] != n && heights[ansArr[i][1]] == heights[i]){
            ansArr[i][1] = ansArr[ansArr[i][1]][1];
        }
    }
    //计算答案
    for(int i=0;i<n;i++){
        ans = Math.max((ansArr[i][1] - ansArr[i][0] -1)*heights[i],ans);
    }
    return ans;
}

简化分析相等情况因为就算相等你也给我弹出，可能这时你无法得到你对应的最大值。但你的那个最后一个相等的就会帮你结算你的最大值！

public static int largestRectangleArea(int[] heights) {
    int n =heights.length;
    size = 0;
    int ans = 0;
    for(int i =0;i<n;i++){
        while(size>0 && heights[stack[size-1]] >= heights[i]){
            int temp = stack[--size];
            int left = size == 0 ? -1 : stack[size-1];
            int right = i;
            ans = Math.max((right-left-1)*heights[temp],ans);
        }
        stack[size++] = i;
    }
    while(size>0){
        int temp = stack[--size];
        int left = size==0? -1 :stack[size-1];
        int right = n;
        ans = Math.max((right-left-1)*heights[temp],ans);
    }
    return ans;
}

最大矩形

leetcode 85

思路：压缩数组！把问题转化为以每一行作为底部时的最大矩形问题跟上一题一样。每一个的高度就是从该行开始连续的1的个数。

   public static int maximalRectangle(char[][] grid) {
	int n = grid.length;
	int m = grid[0].length;
	Arrays.fill(height, 0, m, 0);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		// 来到i行，长方形一定要以i行做底！
		// 加工高度数组(压缩数组)
		for (int j = 0; j < m; j++) {
			height[j] = grid[i][j] == '0' ? 0 : height[j] + 1;
		}
		ans = Math.max(largestRectangleArea(m), ans);
	}
	return ans;
}

public static int largestRectangleArea(int m) {
	r = 0;
	int ans = 0, cur, left;
	for (int i = 0; i < m; i++) {
		// i -> arr[i]
		while (r > 0 && height[stack[r - 1]] >= height[i]) {
			cur = stack[--r];
			left = r == 0 ? -1 : stack[r - 1];
			ans = Math.max(ans, height[cur] * (i - left - 1));
		}
		stack[r++] = i;
	}
	while (r > 0) {
		cur = stack[--r];
		left = r == 0 ? -1 : stack[r - 1];
		ans = Math.max(ans, height[cur] * (m - left - 1));
	}
	return ans;
}

非经典用法

下面的题目利用单调栈思想，而不是经典的用法。

总结

最大宽度坡

leetcode 962

思路：先进行一次遍历把可能作为坡的起点的下标找到。怎么找？每次只入栈比当前栈顶元素更小的元素。为什么？因为如果我比栈顶大，我找到一个坡的终点，那么栈顶元素它比我的下标还要小，那他跟这个坡的终点构成的坡宽度肯定比我大，所以我没资格入栈。

然后倒着遍历找坡的终点。一旦栈顶的元素发现一个值可以作为自己终点那么弹出，并且这个坡就是以自己为起点的最大坡，为什么？因为当前终点已经是最靠右边的索引了，再往前遍历得到的结果只会更小！循环一直把栈里面的元素全部弹出。

public int maxWidthRamp(int[] nums) {
    size = 0;
    int n = nums.length;
    stack[size++] = 0;
    //找可能的起点入栈
    for(int i =1;i<n;i++){
        if(nums[i] < nums[stack[size-1]]){
            stack[size++] = i;
        }
    }
    //倒着遍历找终点
    int i = n-1;
    int ans = 0;
    while(size > 0 && i>=0){
        while( size > 0 && nums[stack[size-1]] <= nums[i]){
            ans = Math.max(ans,i-stack[size-1]);
            size--;
        }
        i--;
    }
    return ans;
}

去除重复字母

leetcode 316

思路：单调栈大压小，遇到更小的尽量往前面走，但有条件限制，即被弹出的元素还有剩余。

public static String removeDuplicateLetters(String str) {
		r = 0;
		Arrays.fill(cnts, 0);
		Arrays.fill(enter, false);
		char[] s = str.toCharArray();
		for (char cha : s) {
			cnts[cha - 'a']++;
		}
		for (char cur : s) {
			// 从左往右依次遍历字符，a -> 0 b -> 1 ... z -> 25
			// cur -> cur - 'a'
			if (!enter[cur - 'a']) {
                // 栈顶元素比当前元素大，并且栈顶元素还有剩余，那么弹出栈顶元素
				while (r > 0 && stack[r - 1] > cur && cnts[stack[r - 1] - 'a'] > 0) {
					enter[stack[r - 1] - 'a'] = false;
					r--;
				}
				stack[r++] = cur;
				enter[cur - 'a'] = true;
			}
			cnts[cur - 'a']--;
		}
		return String.valueOf(stack, 0, r);
	}

大鱼吃小鱼

leetcode 2289

public static final int Max = 100001;

public static int[][] stackT = new int[Max][2];

public static int r ;

public static int cnt;

public int totalSteps(int[] nums) {
    int n =nums.length;
    r = 0;
    int ans = 0;
    for(int i =n-1;i>=0;i--){
        cnt = 0;
        while( r > 0 && stackT[r-1][0] < nums[i]){
            cnt = Math.max(cnt+1,stackT[r-1][1]);
            r--;
        }
        stackT[r][0] = nums[i];
        stackT[r++][1] = cnt;
        ans = Math.max(ans,cnt);
    }
    return ans;
}