單調棧

来源:https://www.cnblogs.com/sxy666666/archive/2023/02/02/17085933.html
-Advertisement-
Play Games

顧名思義單調棧就是具有單調性的棧 ==常見模型:找出每個數左邊離它最近的比它大/小的數== 【演算法】 int stk[N],tt = 0; // 棧中存數據 for (int i = 1; i <= n; i ++){ int x; cin >> x; while (tt && stk[tt] >= ...


顧名思義單調棧就是具有單調性的棧

常見模型:找出每個數左邊離它最近的比它大/小的數

  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;
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 隨著移動互聯網發展,手機端購物已成為人們生活的常態。人們在搜索商品時採用的手段也越來越豐富,當前的主要搜索方式是文本搜索與拍照搜索。 ...
  • 1 簡介 之前在文章《dapr入門與本地托管模式嘗試》中介紹了dapr和本地托管,本文我們來介紹如果在代碼中使用dapr的服務調用功能,並把它整合到Spring Boot中。 Dapr服務調用的邏輯如下: 本次實驗會創建兩個服務: pkslow-data,提供數據服務,用於返回數據; pkslow- ...
  • /*C Primer Plus (7.11) 3*/ 1 #include<stdio.h> 2 int main() 3 { 4 double weight,height; 5 printf("Please enter your weight and height.\n"); 6 printf(" ...
  • 這篇文章主要討論如何在不知道介面的情況下進行RPC調用,以及如何在一個線上系統中支持多種不同的RPC協議。 ...
  • Java版本 JavaSE 標準版,用於桌面程式、控制台等,這是最核心的部分,需要首先學習 JavaME 嵌入式開發,用於家電等(很少用) JavaEE 企業級,用於web、伺服器 一些概念 JDK Java Development Kit,Java開發工具。包含JRE、JVM,且包含一些開發工具( ...
  • 題目描述 給定一個 n 個元素有序的(升序)整型數組 nums 和一個目標值 target ,寫一個函數搜索 nums 中的 target,如果目標值存在返回下標,否則返回 -1。 來源:力扣(LeetCode) 鏈接:https://leetcode.cn/problems/binary-sear ...
  • 第一種:for in girl_dict= {"China": "小美", "Japan": "圖多天光", "Korea": "斯密達美"} for everyKey in girl_dict: print ("key:" + everyKey + "value:" + girl_dict[eve ...
  • Word文檔屬性包括常規、摘要、統計、內容、自定義。其中摘要包括標題、主題、作者、經理、單位、類別、關鍵詞、備註等項目。屬性相當於文檔的名片,可以添加你想要的註釋、說明等。還可以標註版權。 今天就為大家介紹一下,如何通過Java代碼向Word文檔添加文檔屬性。詳情請閱讀以下內容。 將內置文檔屬性添加 ...
一周排行
    -Advertisement-
    Play Games
  • 概述:在C#中,++i和i++都是自增運算符,其中++i先增加值再返回,而i++先返回值再增加。應用場景根據需求選擇,首碼適合先增後用,尾碼適合先用後增。詳細示例提供清晰的代碼演示這兩者的操作時機和實際應用。 在C#中,++i 和 i++ 都是自增運算符,但它們在操作上有細微的差異,主要體現在操作的 ...
  • 上次發佈了:Taurus.MVC 性能壓力測試(ap 壓測 和 linux 下wrk 壓測):.NET Core 版本,今天計劃準備壓測一下 .NET 版本,來測試並記錄一下 Taurus.MVC 框架在 .NET 版本的性能,以便後續持續優化改進。 為了方便對比,本文章的電腦環境和測試思路,儘量和... ...
  • .NET WebAPI作為一種構建RESTful服務的強大工具,為開發者提供了便捷的方式來定義、處理HTTP請求並返迴響應。在設計API介面時,正確地接收和解析客戶端發送的數據至關重要。.NET WebAPI提供了一系列特性,如[FromRoute]、[FromQuery]和[FromBody],用 ...
  • 原因:我之所以想做這個項目,是因為在之前查找關於C#/WPF相關資料時,我發現講解圖像濾鏡的資源非常稀缺。此外,我註意到許多現有的開源庫主要基於CPU進行圖像渲染。這種方式在處理大量圖像時,會導致CPU的渲染負擔過重。因此,我將在下文中介紹如何通過GPU渲染來有效實現圖像的各種濾鏡效果。 生成的效果 ...
  • 引言 上一章我們介紹了在xUnit單元測試中用xUnit.DependencyInject來使用依賴註入,上一章我們的Sample.Repository倉儲層有一個批量註入的介面沒有做單元測試,今天用這個示例來演示一下如何用Bogus創建模擬數據 ,和 EFCore 的種子數據生成 Bogus 的優 ...
  • 一、前言 在自己的項目中,涉及到實時心率曲線的繪製,項目上的曲線繪製,一般很難找到能直接用的第三方庫,而且有些還是定製化的功能,所以還是自己繪製比較方便。很多人一聽到自己畫就害怕,感覺很難,今天就分享一個完整的實時心率數據繪製心率曲線圖的例子;之前的博客也分享給DrawingVisual繪製曲線的方 ...
  • 如果你在自定義的 Main 方法中直接使用 App 類並啟動應用程式,但發現 App.xaml 中定義的資源沒有被正確載入,那麼問題可能在於如何正確配置 App.xaml 與你的 App 類的交互。 確保 App.xaml 文件中的 x:Class 屬性正確指向你的 App 類。這樣,當你創建 Ap ...
  • 一:背景 1. 講故事 上個月有個朋友在微信上找到我,說他們的軟體在客戶那邊隔幾天就要崩潰一次,一直都沒有找到原因,讓我幫忙看下怎麼回事,確實工控類的軟體環境複雜難搞,朋友手上有一個崩潰的dump,剛好丟給我來分析一下。 二:WinDbg分析 1. 程式為什麼會崩潰 windbg 有一個厲害之處在於 ...
  • 前言 .NET生態中有許多依賴註入容器。在大多數情況下,微軟提供的內置容器在易用性和性能方面都非常優秀。外加ASP.NET Core預設使用內置容器,使用很方便。 但是筆者在使用中一直有一個頭疼的問題:服務工廠無法提供請求的服務類型相關的信息。這在一般情況下並沒有影響,但是內置容器支持註冊開放泛型服 ...
  • 一、前言 在項目開發過程中,DataGrid是經常使用到的一個數據展示控制項,而通常表格的最後一列是作為操作列存在,比如會有編輯、刪除等功能按鈕。但WPF的原始DataGrid中,預設只支持固定左側列,這跟大家習慣性操作列放最後不符,今天就來介紹一種簡單的方式實現固定右側列。(這裡的實現方式參考的大佬 ...