力扣1793.好子数组的最大分数

力扣1793.好子数组的最大分数

• 

  • 对于每个数 求其左右两侧小于它高度的元素下标(单调栈)

•   class Solution {
    public:
        int maximumScore(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> left(n,-1);
            stack<int> st;
            for(int i=0;i<n;i++)
            {
                while(!st.empty()&& nums[i] <= nums[st.top()])
                    st.pop();
                if(!st.empty())
                    left[i] = st.top();
                st.emplace(i);
            }
            vector<int> right(n,n);
            //清空st
            st = stack<int> ();
            for(int i=n-1;i>=0;i--)
            {
                while(!st.empty()&& nums[i] <= nums[st.top()])
                    st.pop();
                if(!st.empty())
                    right[i] = st.top();
                st.emplace(i);
            }
    
            int res=0;
            for(int i=0;i<n;i++)
            {
                int h = nums[i],l = left[i],r = right[i];
                if(l<k && k<r)
                    res = max(res,h * (r - l - 1));
            }
            return res;
        }
    };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36