1793. 好子数组的最大分数
思路：单调栈
1遍历数组，用单调栈来找到该位置左边比该位置小的数，存储进数组left中
2.清空栈，再找该位置右边比该位置小的数，存储进数组right中
3 遍历每个位置，计算以当前位置元素为中心时的得分，并找出最大得分。
代码：
class Solution {
public int maximumScore(int[] nums, int k) {
// 单调栈
int n = nums.length;
int[] left = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
// 构建左边第一个比当前元素小的索引
for (int i = 0; i < n; i++) {
int x = nums[i];
while (!stack.isEmpty() && x <= nums[stack.peek()]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
int[] right = new int[n];
// 构建右边第一个比当前元素小的索引
for (int i = n - 1; i >= 0; i--) {
int x = nums[i];
while (!stack.isEmpty() && x <= nums[stack.peek()]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
int ans = 0;
// 计算每个位置得分并找出最大得分
for (int i = 0; i < n; i++) {
int min = nums[i];
int l = left[i];
int r = right[i];
if (l < k && k < r) {
ans = Math.max(ans, min * (r - l - 1));
}
}
return ans;
}
}
