题意

给定一个长度为的数组。找它的长度为的区间中的最大值，求这些所有的最大值的集合里的最小值。

思路

  1. 利用单调栈，对于每一个，找出来左边第一个比它大的，找出来右边第一个比它大的。并且把它们的下标分别存和里。
  2. 对于每一个，它能作为最小值的最长区间已经确定了。那么就可以通过比较得到一部分长度的区间的最优答案了。
    如样例1，执行到这里的时候就是
    [1,3,1061109567,1061109567,5,6]
  3. 此时区间长度为3和4的时候，最小的可选最大值仍未确定。那么就应该从高位继承。
    为什么是从高位继承呢？因为要选定的是集合的最大值，而高位的值必然是低位的值的可选项，而低位的则未必是高位的可选项。

Solution

class Solution {
   public:
    static const int N = 1e5 + 5;
    int L[N], R[N], s[N], t;
    vector<int> getMinimums(vector<int>& a) {
        int n = a.size();
        s[t = 0] = -1;
        for (int i = 0; i < n; ++i) {
            while (t && a[s[t]] <= a[i]) --t;
            L[i] = s[t];  //左边第一个比a[i]大的下标
            s[++t] = i;
        }
        s[t = 0] = n;
        for (int i = n - 1; ~i; --i) {
            while (t && a[s[t]] <= a[i]) --t;
            R[i] = s[t];  //右边第一个比a[i]大的下标
            s[++t] = i;
        }
        /*
        -1 -1 -1 2 2 -1
        1 2 5 4 5 6
        */
        vector<int> ans(n, 0x3f3f3f3f);
        for (int i = 0; i < n; ++i)   // a[i]作为最大值的最长区间
            ans[R[i] - L[i] - 2] = min(ans[R[i] - L[i] - 2], a[i]);
        for (int i = n - 2; ~i; --i)  // 自高位继承
            ans[i] = min(ans[i], ans[i + 1]);
        return ans;
    }
};