一、目錄
? ? ? ? ? ? 1、單調隊列
? ? ? ? ? ? 2、單調棧
二、正文
1.單調棧題型:
(1)給出一個數組找出其中每個數左邊第一個比它小(大)的數字????????????????
????????830. 單調棧 - AcWing題庫
(2)求直方圖中最大的矩形(找出每個數左邊和右邊第一個比它小的數字)
????????131. 直方圖中最大的矩形 - AcWing題庫
(3)?求部分點被破壞的直方圖中最大的矩形((2)的變形)
????????1413. 矩形牛棚 - AcWing題庫
? ? ? ? ?A-玉蟾宮_hunau暑假集訓2——單調棧與單調隊列 (nowcoder.com)
2.單調隊列題型:
(1)一維滑動窗口
? ?????????154. 滑動窗口 - AcWing題庫
(2)二維滑動窗口
? ?? ?D-理想正方形_hunau暑假集訓2——單調棧與單調隊列 (nowcoder.com)
(3)最長上升子序列樸素
? ??895. 最長上升子序列 - AcWing題庫
(4)最長上升子序列線性優化
? ??AcWing 896. 最長上升子序列 II - AcWing
3.對于單調隊列的理解與應用
?(1)?單調隊列可以很好的在某種限制下去處理一個區間的單調數據。
???????P8661 [藍橋杯 2018 省 B] 日志統計 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)?
? ??(2)單調隊列可用于靜態求出區間內的最值
? ? ? ?
?4.對單調棧的理解與應用
????????P7399 [COCI2020-2021#5] Po - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)