单调栈与单调队列

单调栈

原理

  单调栈使用范围比较小，已知有两种用法，其中第一种用法比较经典，用的较多，第二种用法出现较少。

  1. 寻找数组中某一个数左边、右边第一个比它大或小的数。首先要找到最近的一个数，并且满足这个数和当前数的单调关系（比它大或者小）。栈的特点是后进先出，在这里其实利用了栈“最近”的思想，而单调性能够确保与栈顶比较时，相当于比较了所有之前的数据，降低了时间复杂度。

      Condition 1 ：以寻找数列中每一个数左边第一个比它小的数为例，如果使用单调递增栈，当前元素大于栈顶元素，则相当于大于栈中所有元素，当前元素左侧第一个比它小的数就是栈顶元素；

      Condition 2 ：如果当前元素小于栈顶元素，那么当前元素左侧比当前元素还大的那些元素（即已经在栈中）就永远不需要考虑了（我要找的是更小的！），并且可以在这个过程中直接出栈。原因是，这些出栈的元素在更靠后的元素考虑时，肯定不会是答案，因为使得这个元素出栈的元素，会距离更近且更小，具体看下图会更加清晰。可以看到，4号元素在找左侧更小的元素时，一定不会找到2号元素，因为3号元素一定更早被选择。

  2. 寻找数组中两个数之间满足i < j 且 A[i] <= A[j]的情况下，下标之间的最大距离。这种可以看做全局的单调性和“最近”性质的应用，并且还有双指针的思想。这里有个重点是，当从右向左考虑元素时，只需要考虑当前元素左侧是否会产生最大值，不用考虑右侧的情况，因为右侧已经考虑过了。首先从左向右初始化单调递减栈，之后从右向左每次元素和栈顶元素比较，通过出栈每次确认当前最小的元素是否更新了答案，直到栈顶元素大于当前遍历元素：

      Condition 1 ：如果当前元素小于栈顶（当前最小值），则栈内其他元素均不满足A[i] <= A[j]的要求，更进一步说明栈顶元素左侧所有元素均无法产生答案；栈顶右侧元素一定已经和当前元素右侧的元素更新过答案（因此才被弹出栈），所以再和当前元素产生的答案，肯定无法更新答案（从右向左，每次都在递减）。

      Condition 2 ：如果当前元素大于栈顶，由于栈顶元素右边的元素更靠近序列右侧，所以最大距离一定更小，即便和当前元素能产生正确大小关系，也不会更新答案。之后我们无法确定左侧元素是否还能继续产生更大答案，所以栈顶元素出栈，继续比较。能够安全出栈的原因是，右侧当前元素每次都在减少，因此贪心的认为，之后即便有满足要求的元素，也不会更新最大距离（与第一种情况的栈顶右侧元素一致）。

  假设序列是 A B C D E F G H，从左到右入递减栈的是A B D，那么假设当前元素为G：

  1. 如果G >= D，D出栈，考虑B，如果G >= B, 即使G >= C没有产生更大答案，如果G < B，因为从左到右是单调栈，因此C > B, 若G > C，可以推导出C < G < B, B > C，冲突，所以不用考虑G > C的情况。
  2. 如果G < D, 比最小值还小，那么栈顶元素左侧没有可以满足条件的情况；而右侧E F即便有更小，也无法更新答案。

模板

//寻找数组中某一个数左边第一个比他大的数
for (int i = 0; i < n; i ++ )
{
    while (!st.size() && s[i] >= st.top()) st.pop();
    if (st.size()) cout << st.top() << " ";
    else cout << "-1 ";
    st.push(s[i]);
}

//寻找i < j 且 A[i] < A[j]条件的最大j - i
stack<int> st;
int n = A.size();
for (int i = 0; i < n; i ++ )
    if (st.empty() || A[i] < A[st.top()])
        st.push(i);

int ans = 0;
for (int i = n - 1; i >= 0; i -- )
{
    while (st.size() && A[i] >= A[st.top()])
    {
        ans = max(ans, i - st.top());
        st.pop();
    }
    if (!st.size()) break;
}

return ans;

例题

AW.830 单调栈（简单）

LC.739 每日问题（中等）

LC.42 接雨水（困难）

LC.84 柱状图中最大的矩形（困难）

LC.962 最大宽度坡（中等）

单调队列

原理

  单调队列是队头维护的是整个队列中最大或者最小的元素，每次有新元素入队时，如果不满足当前队列维护的单调性，则将所有不满足的元素全部出队。单调队列本质是一个双端队列，每次出队时是从队尾出队，而不是从队头出队。单调队列可以解决滑动窗口的最值问题，以及与之相关的优化。

  单调队列操作顺序也比较重要，在不同需要的时候有不同的操作顺序。

  1. 计算是否当前元素和队头元素距离之差大于规定值，如果大于则队头出队。
  2. 计算答案，此时是计算的[0, r - 1]范围内的最值，因此放在第二步。
  3. 保持队列单调性，while循环从队尾出队。
  4. 将当前元素入队。
  5. *若计算答案在这里，则是求的[0, r]范围内的最值。

模板

//k是窗口大小, 计算最大值, 手动模拟队列
int q[N];
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    //如果下标是不连续的，这里要写while，因为这里每次最多下标+1所以可以写if
    if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
    //这里大于等于和大于都能过，但是推荐写大于等于，当相等的时候，每次只保留最新的一个即可
    while (hh <= tt && a[i] >= a[q[tt]]) tt -- ;
    q[ ++ tt ] = i;
    //这里事实上求的[0, i]范围的最值
    if (i >= k - 1) cout << a[q[hh]] << " ";
}

//stl版本
deque<int> q;
for (int i = 0; i < n; i ++ )
{
    if (q.size() && i - q.front() + 1 > k) q.pop_front();
    //这里求的是[0, i - 1]的最值
    if (i >= k - 1) cout << a[q.front()] << " ";
    while (q.size() && a[i] <= a[q.back()]) q.pop_back();
}

例题

AW.154 滑动窗口（简单）

LC.1499 满足不等式的最大值（困难）

赏

庄敬日强，功不唐捐。