1793. Maximum Score of a Good Subarray

,

Stack

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
37
class Solution {
    public int maximumScore(int[] nums, int k) {
        Stack<Integer> increaseStack = new Stack<>(); // 非严格单调递增栈

        int[] left = new int[nums.length]; // 左侧更小元素的索引
        for (int i = 0; i < nums.length; i++) {
            while (!increaseStack.isEmpty() && nums[i] <= nums[increaseStack.peek()]) {
                increaseStack.pop();
            }

            left[i] = increaseStack.isEmpty() ? -1 : increaseStack.peek();
            increaseStack.push(i);
        }

        increaseStack.clear();

        int[] right = new int[nums.length]; // 右侧更小元素的索引
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!increaseStack.isEmpty() && nums[i] <= nums[increaseStack.peek()]) {
                increaseStack.pop();
            }

            right[i] = increaseStack.isEmpty() ? nums.length : increaseStack.peek();
            increaseStack.push(i);
        }

        int maxScore = 0;
        for (int i = 0; i < nums.length; i++) {
            int leftIndex = left[i], rightIndex = right[i];
            if (leftIndex < k && k < rightIndex) { // 注意 leftIndex 和 rightIndex 均为不在面积内的边界，所以此处比较时不能相等
                maxScore = Math.max(maxScore, nums[i] * (rightIndex - leftIndex - 1));
            }
        }

        return maxScore;
    }
}

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;

        int maxScore = nums[k]; // 注意此处的初始值，当数组仅有一个元素时无法进入循环更新值，所以此处必须显式赋值
        int i = k, j = k, minHeight = nums[k]; // 区间：[i, j]

        int times = n - 1; // 最多扩张 n - 1 次
        while (times > 0) {
            if (j == n - 1 || (i > 0 && nums[i - 1] > nums[j + 1])) {
                i--;
                minHeight = Math.min(minHeight, nums[i]);
            } else {
                j++;
                minHeight = Math.min(minHeight, nums[j]);
            }

            maxScore = Math.max(maxScore, minHeight * (j - i + 1));
            times--;
        }

        return maxScore;
    }
}

References

1793. Maximum Score of a Good Subarray