Problem: 1793. 好子数组的最大分数

💖 单调栈

思路

👨‍🏫 参考题解

• 以当前高度为基准，寻找最大的宽度
• 组成最大的矩形面积那就是要找左边第一个小于当前高度的下标left，再找右边第一个小于当前高度的下标right
• 那宽度就是这两个下标之间的距离了 但是要排除这两个下标（开区间） 所以是 right-left-1 用单调栈就可以很方便确定这两个边界了

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int[] left = new int[n];//left[i] 存左边比 nums[i] 小的第一个下标，没有则存 -1
        Deque<Integer> st = new ArrayDeque<>();//单调递增栈
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (!st.isEmpty() && x <= nums[st.peek()]) {
                st.pop();
            }
            // 左边没有比当前元素小的，存 -1
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        int[] right = new int[n];//right[i] 存右边比 nums[i] 小的第一个下标，没有则存 -1
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            int x = nums[i];
            while (!st.isEmpty() && x <= nums[st.peek()]) {
                st.pop();
            }
            right[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int h = nums[i];
            int l = left[i];
            int r = right[i];
            if (l < k && k < r) { 
                ans = Math.max(ans, h * (r - l - 1));//开区间不包含边界
            }
        }
        return ans;
    }
}

💖 双指针[TODO]

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int ans = nums[k], minH = nums[k];
        int i = k, j = k;
        for (int t = 0; t < n - 1; t++) { // 循环 n-1 次
            if (j == n - 1 || i > 0 && nums[i - 1] > nums[j + 1]) {
                minH = Math.min(minH, nums[--i]);
            } else {
                minH = Math.min(minH, nums[++j]);
            }
            ans = Math.max(ans, minH * (j - i + 1));
        }
        return ans;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximum-score-of-a-good-subarray/solutions/2695415/liang-chong-fang-fa-dan-diao-zhan-shuang-24zl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。