草庐IT

单调栈

sxy666666 2023-03-28 原文

顾名思义单调栈就是具有单调性的栈

常见模型：找出每个数左边离它最近的比它大/小的数

  1. 【算法】
int stk[N],tt = 0;	// 栈中存数据
for (int i = 1; i <= n; i ++){
    int x; cin >> x;
    while (tt && stk[tt] >= x) tt -- ;	// 左边比它小的数
    stk[ ++ tt] = i;	// 把当前值放在合适地方
}
  1. 【应用一】
    直方图中最大的矩形
    算法思想:
    ① 以每一个矩形的高为标准，找出左右两边第一个小于此矩形高的矩形，枚举所有
    的矩形，找出最大面积。
    ② 利用单调栈，进行预处理将每个矩形左右两边的第一个小于此矩形高的矩形。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 100010;
int n;// h: 高度 q: 单调栈->记录h的下标 l: 左边符合条件距离 r: 右边符合条件距离
int h[N],q[N],l[N],r[N];
void solve(){
    while (scanf("%d", &n),n){
        for (int i = 1; i <= n; i ++) scanf("%d",&h[i]);
        h[0] = h[n + 1] = -1;      // 预处理要边界条件
        // 找出左边第一个高度小于当前
        int tt = -1;
        q[++ tt] = 0;   // 下标 0
        for (int i = 1; i <= n; i ++){
            while (h[q[tt]] >= h[i]) tt --;//维护好单调栈: 找到栈中第一个小于当前值的数据
            l[i] = i - q[tt];   // 记录i左边第一符合条4 件的数据距离
            q[++ tt] = i;       // 当前值下标入栈
        }
        // 同理求右边
        tt = -1;
        q[++ tt] = n + 1;
        for (int i = n; i >= 1; i --){
            while (h[q[tt]] >= h[i]) tt --;
            r[i] = q[tt] - i;
            q[++ tt] = i;
        }
        LL res = 0;
        for (int i = 1; i <= n; i ++)
            res = max(res, (LL)h[i] * (l[i] + r[i] - 1));// - 1是因为计算左右两边就多加一个h[i]
        printf("%lld\n", res);
    }
}
int main(){
    solve();
    return 0;
}
  1. 【应用二】
    城市游戏
    算法思想:
    联想【应用一】，统计每一行向上的高度，再利用应用一单调栈的解题方法，遍历n行，求出最优解。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N = 1010;
int n,m,res;
int h[N],q[N],l[N],r[N];
// 这里就是【应用一】一行的解题方法
void solve(){
    for (int i = 0; i <= m + 1; i ++)q[i] = 0;
    h[0] = h[m + 1] = -1;
    int tt = -1;
    q[++ tt] = 0;
    for (int i = 1; i <= m; i ++){
        while (h[q[tt]] >= h[i]) tt --;
        l[i] = i - q[tt];
        q[++ tt] = i;
    }
    tt = -1;
    q[++ tt] = m + 1;
    for (int i = m; i >= 1; i --){
        while (h[q[tt]] >= h[i]) tt --;
        r[i] = q[tt] - i;
        q[++ tt] = i;
    }
    for (int i = 1; i <= m; i ++)
        res = max(res, h[i] * (l[i] + r[i] - 1));
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++){
        for (int j = 1; j <= m; j ++){
            char c; cin >> c;   // 这里建议用cin 自动省略空格回车
            if (c == 'R') h[j] = 0;  // 遇R高度就变0
            else h[j] += 1;
        }
        solve();
    }
    printf("%d\n", res * 3);
    return 0;
}
单调intttC++

有关单调栈的更多相关文章

  1. javascript - 在 Node.js 中单调增加时间 - 2

    浏览器已经回答了这个问题here，但是window.performance.now()在Node.js中显然不可用。一些应用程序需要稳定的时钟，即随时间单调增加的时钟，不受系统时钟漂移的影响。例如，Java有System.nanoTime()而C++有std::chrono::steady_clock.Node.js中有这样的时钟吗？ 最佳答案 原来Node.js中的等价物是process.hrtime().根据文档:[Thetimereturnedfromprocess.hrtime()is]relativetoanarbitra

  2. windows - QueryUnbiasedInterruptTime 是单调的吗？ - 2

    我正试图在Windows上为clock_gettime(CLOCK_MONOTONIC)和mach_absolute_time找到合适的替代品。GetTickCount很烦人，因为它故意有偏见:当系统从挂起或休眠状态恢复时，Windows似乎计算出它被挂起的时间(从主板)然后将其添加到滴答计数中以使得它看起来像是在系统断电时继续滴答作响。QueryUnbiasedInterruptTime更友好:它是一个简单、看似可靠的计数器，只返回系统自启动以来运行的时间。现在，我已经对QueryUnbiasedInterruptTime进行了试验，以了解当计算机进入以下每种状态时会发生什么:sle

  3. 由 html 表单调用时在浏览器上显示代码的 Php 文件 - 2

    每当在我的网络应用程序中调用我的php文件时，代码就会显示在浏览器上。之前，我在Windows上使用open和notepad++选项打开了.php文件。现在每次我点击或运行.php文件时，它默认使用notepad++打开。任何修复？ 最佳答案 一旦你用notepad++打开了.php文件，它就变成了默认的.php文件。因此，无论何时您以后打开.php文件，它都会在Notepad++中打开。您可以随时更改它。 关于由html表单调用时在浏览器上显示代码的Php文件，我们在StackOver

  4. javascript - 在 JavaScript 中单调增加时间？ - 2

    在JavaScript中获得单调递增时间的最佳方法是什么？我希望有类似Java的System.nanoTime()的东西。Date()显然是行不通的，因为它受系统时间变化的影响。换句话说，我想要的是always:a=myIncreasingTime.getMilliseconds();...//sometimelater,maybeseconds,maybedaysb=myIncreasingTime.getMilliseconds();充其量，即使在Date()中使用UTC函数，它也会返回它认为是正确的时间，但如果有人将时间向后设置，下一次调用Date()可以返回一个较小的值。Sys

  5. java - 单调对 - Codility - 2

    我刚刚在Codility，遇到了一个任务，我找不到目标O(n)效率的解决方案；我的解决方案运行时间为O(n2)。如果有人能给我一些关于如何让它运行得更快的提示，我将非常高兴。这是任务。给定一个由N个整数组成的非空零索引数组A。monotonic_pair是一对整数(P,Q)，满足0≤P≤Q目标是找到索引相距最远的单调对。更准确地说，我们应该最大化Q−P的值。仅找到距离就足够了。例如，考虑这样的数组A:A[0]=5A[1]=3A[2]=6A[3]=3A[4]=4A[5]=2有十一个单调对:(0,0),(0,2),(1,1),(1,2),(1,3),(1,4),(2,2),(3,3),(3

  6. c++ - 使用单调多边形的多边形三角剖分 - 2

    我有一个没有孔的简单多边形，需要将其三角化为凸多边形以便在物理引擎中使用，而且我可以使用这些凸多边形通过三角形带进行渲染。This维基百科文章展示了如何使用单调多边形对多边形进行三角剖分。它提供了它如何工作的简短描述，但不够详细，我无法理解。这种方法似乎非常适合我的需要，FlashDemo它链接到表明该算法非常适合我的需要。我一直在谷歌上搜索以寻找对算法的更好解释，但我只能找到进行三角剖分的库或源代码。我更愿意学习它是如何工作的并编写我自己的方法，但如果我需要使用预先编写的库，它就必须这样做。任何人都可以提供解释或资源来说明我如何了解这种三角测量的工作原理吗？

  7. c++ - 在 C++ 中获得可靠的单调时间(多平台) - 2

    我需要一个可用于计算间隔的单调时钟。要求:必须是单调的，不能受设备时间的影响。在应用程序session期间不得重置。(session中所有返回值的相同纪元)必须代表现实生活中的秒数(不是cpu秒数)，不得受当时运行的线程/进程数的影响。秒解决就足够了。在我的研究中我发现候选人:std::clock()(ctime)-似乎使用cpu秒数boost::chrono::steady_clock()-它使用cpu秒吗？在应用程序session(launch-end)期间epoch可以改变吗？平台特定方法(clock_gettime、mach_absolute_time)。您是否遇到过这样的问题

  8. c++ - 在没有单调时钟的系统上是否不可能实现一致？ - 2

    header定义类steady_clock表示单调时钟-即now()的值永远不会随着物理时间的增加而减少。虽然此类未标记为可选，但如果因为它在没有单调时间源的系统上运行而无法实现它，会发生什么情况？查看libstdc++源代码，以_GLIBCXX_USE_CLOCK_MONOTONIC为例未定义，steady_clock简单地定义为:typedefsystem_clocksteady_clock;system_clock虽然不一定稳定，所以这可能(并且可能会)打破steady_clock的要求.在没有单调时间源的系统上是否不可能实现C++11的一致性？为什么不直接制作steady_cl

  9. c++ - steady_clock 跨线程是单调的吗？ - 2

    std::chrono::steady_clock的单调属性是否跨线程保留？例如，假设我有以下程序。#include#include#includeusingnamespacestd;usingnamespacechrono;mutexm;inti=0;voiddo_something(int&x){x+=1;}voidf1(){unique_locklock(m);autotime=steady_clock::now();do_something(i);}voidf2(){unique_locklock(m);autotime=steady_clock::now();do_somet

  10. windows - Windows是否为应用程序提供单调递增的时钟 - 2

    这个问题的灵感来自DoesLinuxprovideamonotonicallyincreasingclocktoapplications.也许我应该更准确:我正在寻找一个时钟函数，它是strictlyincreasing，因此永远不会返回相同的值，这与两个调用相互跟随的速度无关。 最佳答案 是的，GetTickCount()做这个。如果您想要更高保真度的计数器，QueryPerformanceCounter也可用。这些计数器都不依赖于一天中的时间。 关于windows-Windows是否

随机推荐