C/C++教程

Acwing单调栈

本文主要是介绍Acwing单调栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1 题目描述
在这里插入图片描述

2 思路
1.用一个栈保存当前元素以前的序列,栈用一个数组来表示
2.栈中序列是单调递增的 当i<=j a[i]>=a[j]时,delete(a[i]) 保证剩余的序列一定是单调的

3 代码

package chapter02;

import java.io.IOException;
import java.util.Scanner;

/**
 * @author mys
 * @date 2022/3/21 17:44
 */
public class p830 {
    static int N = 100010;
    public static void main(String[] args) throws IOException {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//数组长度

        //栈
        int[] stk = new int[N];
        int tt = 0;

        for (int i = 0; i < n; i ++) {
            int x = input.nextInt();
            //栈不为空,同时栈顶元素>=x,出栈,保证栈是一个单调递减的栈
            while (tt != 0 && stk[tt] >= x) {
                tt --;
            }
            //如果栈不为空,输出栈顶元素,即比当前元素小的最近的元素,否则输出0
            if (tt != 0) {
                System.out.print(stk[tt] + " ");
            } else {
                System.out.print(-1 + " ");
            }
            //最后把当前元素把x加入到栈中
            stk[++ tt] = x;
        }
    }
}

单调栈leetcode题目:
84. 柱状图中最大的矩形
在这里插入图片描述

暴力解法:遍历高度,往左、右找第一个小于当前元素的位置(类似上面的单调栈),高度乘左右宽度就是的最大值就是所求结果。此写法在LC上能通过,但是时间、空间效率都很低,思路简单。

public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        //left:存放从当前元素位置往做左,直到比当前元素小
        //right:存放从当前元素位置往右,直到比当前元素小或到达右边界
        int[] left = new int[len], right = new int[len];
        Stack<Integer> stk = new Stack<>();

        //从左往右遍历:找左边第一个小于当前位置的元素
        for (int i = 0; i < len; i ++) {
            //如果栈不为空,同时栈顶元素>=当前元素,出栈,保证栈是一个单调递增的序列
            while (! stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
                stk.pop();
            }
            //如果栈不为空,记录栈顶元素,否则为-1
            if (! stk.isEmpty()){
                left[i] = stk.peek();
            } else {
                left[i] = -1;
            }
            //当前元素入栈
            stk.push(i);
        }

        //注意:清空栈
        stk = new Stack<>();

        //从右往左遍历:找右边第一个小于当前位置的元素,没有则是右边界
        for (int i = len - 1; i >= 0; i --) {
            while (! stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
                stk.pop();
            }
            if (! stk.isEmpty()) {
                right[i] = stk.peek();
            } else {
                right[i] = len;
            }
            stk.push(i);
        }

        int res = 0;
        //遍历上边界:找面积最大值
        for (int i = 0; i < len; i ++) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }

未完待续…

这篇关于Acwing单调栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!