===
Index
介绍
单调栈
单调栈是指一个栈内部的元素是具有严格单调性的一种数据结构，分为单调递增栈和单调递减栈。
单调栈有两个性质：
- 1.满足从栈顶到栈底的元素具有严格的单调性
- 2.满足栈的后进先出特性越靠近栈底的元素越早进栈
单调栈主要解决的问题：
- 左边区间第一个比它小的数，第一个比它大的数
- 确定这个元素是否是区间最值
- 右边区间第一个大于它的值
- 到 右边区间第一个大于它的值 的距离
- 确定以该元素为最值的最长区间
单调队列
- 可以查询区间最值（不能维护区间k大，因为队列中很有可能没有k个元素） 优化DP（见参考文献3）
- 用于优化动态规划方面问题的一种特殊数据结构，且多数情况是与定长连续子区间问题相关联
单调队列和单调栈性质
- 具有单调性
- 容器中的元素个数永远不为空。（因为当添加一个元素时，它要么直接被添加到“尾部”，要么弹出k个比它小的数后再被添加到“尾部”）
- 对于一个元素i，我们可以知道在它左边区间，第一个比它小的值, 在元素添加的过程中，我们会不断弹出比它小的值，最后一个弹出的值，即为所求。如果没有元素被弹出，那就无法求出，虽然这个数一定存在。顺便在这里多提一句，第二个比它小的数是一定不知道的，因为不确定是否被弹出
- 对于一个元素i，我们可以知道在它左边区间，第一个比它大的值，也就是𝑀𝑖𝑛(𝑣[𝑥]|𝑥<𝑖&&𝑣[𝑥]>𝑣[𝑖]) 在弹出比i小的所有元素后，栈顶的元素即为所求。如果栈为空，也无法求出。
- 根据2和3，它们是元素插入时所获得的信息，我们可以推出当元素被弹出时能获得的信息：在右边区间，第一个比它大的值。
- 我们可以统计在添加元素过程中，弹出了多少个元素。
单调队列和单调栈相同点：
- 单调队列和单调栈的“头部”都是最先添加的元素，“尾部”都是最后添加的元素。
- 递增和递减的判断依据是：从栈底（队尾）到栈顶（队首），元素大小的变化情况。所以队列和栈是相反的。
- 它们的操作是非常相似的。当队列长度为无穷大时，递增的单调队列和递减的单调栈，排列是一样的！ 原因在于，长度为无穷大的的队列不会在“头部”有popfront操作，而在“尾部”的操作是一模一样的：数据都从“尾部”进入，并按照相同的规则进行比较。
- 两者维护的时间复杂度都是O(n)，因为每个元素都只操作一次。
区别
- 队列可以从队列头弹出元素，可以方便地根据入队的时间顺序（访问的顺序）删除元素。
- 这样导致了单调队列和单调栈维护的区间不同。当访问到第i个元素时，单调栈维护的区间为[0, i)，而单调队列维护的区间为(lastpop, i)
- 单调队列可以访问“头部”和“尾部”，而单调栈只能访问栈顶（也就是“尾部”）。这导致单调栈无法获取[0, i)的区间最大值/最小值。
综上所述，单调队列实际上是单调栈的的升级版。单调栈只支持访问尾部，而单调队列两端都可以。当然，单调栈的编程上（两个函数）比单调队列（三个函数）要简单。
单调队列
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
代码
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
while (!dq.empty() && nums[dq.back()] < nums[i])
dq.pop_back();
dq.push_back(i);
while (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) res.push_back(nums[dq.front()]);
}
return res;
}
滑动窗口最小值
只需要把单调递减栈改为单调递增栈，就可以求滑动窗口最小值了。
vector<int> minSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
while (!dq.empty() && nums[dq.back()] > nums[i])
dq.pop_back();
dq.push_back(i);
while (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) res.push_back(nums[dq.front()]);
}
return res;
}
满足条件的出发点数量
一座环形岛屿上有n个宝箱，顺时针编号1-n，
但是每次开启宝箱将会让派蒙的体力增加或者减少或者不变。最开始派蒙的体力值为 0，一旦派蒙的体力低于 0 ，派蒙就会体力不支而晕倒。
现在派蒙可以从任意一个宝箱地点出发，按顺时针方向开启宝箱，也就是说派蒙可以按 1…n 或者 i,i+1,i+2…n,1,2…i-1 的顺序一个个开启宝箱。
派蒙想知道可以从多少个宝箱地点出发，可以让派蒙开启完所有宝箱，并且全程不晕倒。
分析
如果从i出发，则经过 i,i+1,i+2…n,1,2…i-1 全程不晕倒，需要该数组所有前缀和非负。
将数组复制一遍，求出前缀和，使用滑动窗口最小值维护每长度为n的窗口最小值，然后比较该最小值的前缀和在以i为起始时是否为负。如果大于等于0则满足条件。
如果数据范围小一些，可以使用st表查询区间最小值。
/*
return: res 所有满足条件的起始点下标
*/
vector<int> getValidPos(vector<int> &a) {
int n = a.size(), m = 2 * n;
vector<long long> s(m + 1);
for (int i = 0; i < m; ++i)
s[i + 1] = s[i] + a[i % n];
vector<int> res;
deque<long long> q;
for (int i = 0; i < m; ++i) {
while (q.size() && s[q.back()] > s[i]) q.pop_back();
q.push_back(i);
while (q.front() <= i - n) q.pop_front();
if (i >= n && s[q.front()] >= s[i - n]) {
res.push_back(i - n);
}
}
return res;
}
连续子序列的最大和
给定一个长度为n的整数序列，请找出长度不超过m的连续子序列的最大值
示例 数组 [2, -3, 5, 2, -4, -1, 8] m = 3, 那么长度不超过3的连续子序列的最大和为8.
讲解
设s为数组的前缀和数组，即 s[1] = a[0], s[i] = a[0] + a[1] + … + a[i-1]
则对数组中任意元素a[k-1]，以a[k-1]为结尾的连续子序列的最大和为 s[k] - min(s[k-1], …, s[k-m]) 问题转化为求,用滑动窗口求[k-m, k-1]内的最小值
代码
int maxSum(vector<int>& nums, int m) {
vector<int> s(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); ++i)
s[i] = s[i - 1] + nums[i - 1];
int ans = 0; //
deque<int> dq;
for (int i = 0; i < nums.size(); ++i) {
while (!dq.empty() && s[dq.back()] > s[i])
dq.pop_back();
dq.push_back(i);
while (dq.front() <= i - m) dq.pop_front();
ans = max(ans, s[i + 1] - s[dq.front()]); //
}
return ans;
}
和至少为k的最短子数组
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。 如果没有和至少为 K 的非空子数组，返回 -1 。
讲解
记设s为数组的前缀和数组，即 s[1] = a[0], s[i] = a[0] + a[1] + … + a[i-1] 区间 [i, j]的子数组和为 s[j+1]-s[i] 求 s[j+1]-s[i]>=k 的最短子数组长度 对于任意的j，求以j结尾的满足s[j+1]-s[i]>=k的 j+1-i的最小值。
代码
class Solution {
public:
int shortestSubarray(vector<int>& a, int k) {
int n = a.size(), ans = n + 1;
vector<long long> s(n + 1);
for (int i = 0; i < n; ++i) s[i + 1] = s[i] + a[i];
deque<int> dq;
for (int i = 0; i <= n; ++i) {
while (!dq.empty() && s[dq.back()] > s[i]) dq.pop_back();
dq.push_back(i);
while (!dq.empty() && s[i] - s[dq.front()] >= k) {
ans = min(ans, i - dq.front());
dq.pop_front();
}
}
return ans > n ? -1 : ans;
}
};
和大于等于k的最长连续序列
有一台atm机，初始钱数为t，一个长为n的数组a,a[i]>0表示往atm存钱，a[i]<0表示从atm取钱，可以选择从任意下标开始处理一段连续的数组，当atm的钱小于要取得钱时，atm将关闭，求atm能服务的最长连续数组长度，输出其开始结束下标。
- 1 <= n <= 2e5
- 0 <= t <= 1e9
- -1e9 <= a[i] <= 1e9
分析
方法一：单调队列+二分
如果atm能处理长度为k的 a[l], a[l+1],…a[r] 的连续序列，则a[l..r]的最小前缀和应该大于等于-k。设s为a的前缀和数组，则 min(s[l],..,s[r]) - s[l-1] + k >= 0, 可以对长度k进行二分,对每一个长度，使用单调队列维护长度为k的窗口最小值。
void solve() {
int n, t, x, y;
cin >> n >> t;
vector<long long> s(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> s[i];
s[i] += s[i - 1];
}
auto chk = [&] (int k) {
deque<int> q;
for (int i = 1; i <= n; ++i) {
while (!q.empty() && q.front() <= i - k) q.pop_front();
while (!q.empty() && s[q.back()] >= s[i]) q.pop_back();
q.push_back(i);
if (i >= k) {
long long minv = s[q.front()] - s[i - k] + t;
if (minv >= 0) {
x = i - k + 1, y = i;
return 1;
}
}
}
return 0;
};
int l = 0, r = n;
while (l < r) {
int md = (l + r + 1) / 2;
if (chk(md)) l = md;
else r = md - 1;
}
if (l) cout << x << ' ' << y << "\n";
else cout << "-1\n";
}
方法二：双指针
void solve() {
int n, t;
cin >> n >> t;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
long long s = t;
int mx = 0, x, y, l = 0;
for (int r = 0; r < n; ++r) {
s += a[r];
while (l <= r && s < 0) {
s -= a[l];
l++;
}
if (r - l + 1 > mx) {
mx = r - l + 1, x = l, y = r;
}
}
if (mx) cout << x + 1 << ' ' << y + 1 << '\n';
else cout << "-1\n";
}
单调栈
维护左边和右边第一个比当前元素大的元素
vector<int> lmx(n, -1), rmx(n, n);
stack<int> sk;
for (int i = 0; i < n; ++i) {
while(!sk.empty() && a[sk.top()] < a[i]) {
rmx[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
sk = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!sk.empty() && a[sk.top()] <= a[i]) {
lmx[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
维护左边和右边第一个比当前元素小的元素
vector<int> lmn(n, -1), rmn(n, n);
stack<int> sk;
for (int i = 0; i < n; ++i) {
while(!sk.empty() && a[sk.top()] > a[i]) {
rmn[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
sk = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!sk.empty() && a[sk.top()] >= a[i]) {
lmn[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
代码
vector<int> dailyTemperatures(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 0);
stack<int> sk;
for (int i = 0; i < n; ++i) {
while(!sk.empty() && nums[sk.top()] < nums[i]) {
res[sk.top()] = i - sk.top();
sk.pop();
}
sk.push(i);
}
return res;
}
好子数组的最大分数
给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
请你返回 好 子数组的最大可能 分数 。
代码
int maximumScore(vector<int>& nums, int k) {
int n = nums.size();
vector<int> left(n,-1), right(n,n);
stack<int> sk;
for (int i = 0; i < n; ++i) {
while(!sk.empty() && nums[sk.top()] > nums[i]) {
right[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
sk = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!sk.empty() && nums[sk.top()] > nums[i]) {
left[sk.top()] = i;
sk.pop();
}
sk.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int l = left[i] + 1, r = right[i] - 1;
if (l <= k && r >= k) {
ans = max(ans, (r - l + 1) * nums[i]);
}
}
return ans;
}
左边区间第一个比它小的数
给一个数组，对于每一个元素，找出它之前第一个比它小的元素的值。如果没有，则输出它本身。
样例
输入： list = [2,3,6,1,5,5]
输出：[2,2,3,1,1,1]
解释：依据题意，找出每个数字前面第一个比它小的元素。
vector<int> solve(vector<int>& nums) {
stack<int> sk;
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
while(!sk.empty() && nums[sk.top()] >= nums[i]) {
sk.pop();
}
if (sk.empty()) ans.push_back(nums[i]);
else ans.push_back(nums[sk.top()]);
sk.push(i);
}
return ans;
}
队列中可以看到的人数
有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], …, heights[j-1]) 。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
解析 单调栈，从后往前遍历，关键要点是：如果当前高度大于栈顶，则这个栈顶对于再往前的其他人没有贡献，可以将其弹栈。
vector<int> canSeePersonsCount(vector<int>& a) {
int n = a.size();
stack<int> s;
vector<int> ans(n);
for (int i = n - 1; ~i; --i) {
while (!s.empty() && a[i] > s.top()) {
ans[i]++;
s.pop();
}
if (!s.empty()) ans[i]++;
s.push(a[i]);
}
return ans;
}
使数组按非递减顺序排列
你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。
分析
- 对于每个nums[i],其一定是被 左侧第一个更大的元素（如果有）消除的，可以用单调栈求左侧第一个更大元素。（如果找不到左侧第一个更大元素，那么它永远不会被消除）
- 设 nums[i]被 numsj消除,位于 j 和 i 之间的元素一定被首先消除，使得 nums[j] 和 nums[i]相邻，然后再是 nums[j]消除 nums[i],设 f[i] 为 nums[i]被消除所需的轮数，那么 f[i]=max(f[j+1]…f[i−1])+1。
- 最终的答案就是 max(f[i])。
class Solution {
public:
int totalSteps(vector<int>& a) {
vector<int> f(a.size());
stack<int> s;
for (int i = 0; i < a.size(); ++i) {
int cur = 0;
while (s.size() && a[s.top()] <= a[i]) {
cur = max(cur, f[s.top()]);
s.pop();
}
if (s.size()) f[i] = cur + 1;
s.push(i);
}
return *max_element(f.begin(), f.end());
}
};
