class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
}
};
1793. 好子数组的最大分数
给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
请你返回 好 子数组的最大可能 分数 。
示例 1：
输入：nums = [1,4,3,7,4,5], k = 3 输出：15 解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
示例 2：
输入：nums = [5,5,4,5,4,1,1,1], k = 0 输出：20 解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 2 * 1040 <= k < nums.length原站题解
php 解法, 执行用时: 275 ms, 内存消耗: 25.9 MB, 提交时间: 2024-03-19 09:44:24
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function maximumScore($nums, $k) {
$l = $k;
$r = $k;
$n = count($nums);
$res = 0;
while (true) {
while ($r < $n && $nums[$r] >= $nums[$k]) {
$r++;
}
while ($l >= 0 && $nums[$l] >= $nums[$k]) {
$l--;
}
$res = max($res, ($r - $l - 1) * $nums[$k]);
if ($l < 0 && $r == $n) {
break;
}
if ($l >= 0 && $r < $n) {
$nums[$k] = max($nums[$l], $nums[$r]);
} elseif ($l < 0) {
$nums[$k] = $nums[$r];
} else {
$nums[$k] = $nums[$l];
}
}
return $res;
}
}
golang 解法, 执行用时: 128 ms, 内存消耗: 8.7 MB, 提交时间: 2023-09-25 10:38:52
func maximumScore(nums []int, k int) int {
l, r, n, res := k, k, len(nums), 0 //定义左右边界l r，最大可能分数res
for {
for r < n && nums[r] >= nums[k] {
r++ //向右寻找以nums[k]为最小值的好子数组
}
for l >= 0 && nums[l] >= nums[k] {
l-- //向左寻找以nums[k]为最小值的好子数组
}
res = max(res, (r - l - 1) * nums[k]) //更新最大可能分数
if l < 0 && r == n {
break //遍历完数组，直接退出循环
}
if l >= 0 && r < n {
nums[k] = max(nums[l], nums[r]) //更新nums[k] 为左右边界中的较大者
} else if l < 0 {
nums[k] = nums[r] //左边遍历完了，更新nums[k]为右边界
} else {
nums[k] = nums[l] //右边遍历完了，更新nums[k]为左边界
}
}
return res
}
func max(a, b int) int { if a > b { return a }; return b }
java 解法, 执行用时: 2 ms, 内存消耗: 55.2 MB, 提交时间: 2023-09-25 10:35:04
class Solution {
public int maximumScore(int[] nums, int k) {
int l = k, r = k, n = nums.length, res = 0; //定义左右边界l r，最大可能分数res
while(true){
while(r < n && nums[r] >= nums[k]) r++; //向右寻找以nums[k]为最小值的好子数组
while(l >= 0 && nums[l] >= nums[k]) l--; //向左寻找以nums[k]为最小值的好子数组
res = Math.max(res, (r - l - 1) * nums[k]); //更新最大可能分数
if(l < 0 && r == n) break; //遍历完数组，直接退出循环
if(l >= 0 && r < n) nums[k] = Math.max(nums[l], nums[r]); //更新nums[k] 为左右边界中的较大者
else if(l < 0) nums[k] = nums[r]; //左边遍历完了，更新nums[k]为右边界
else nums[k] = nums[l]; //右边遍历完了，更新nums[k]为左边界
}
return res;
}
}
python3 解法, 执行用时: 132 ms, 内存消耗: 25.4 MB, 提交时间: 2023-09-25 10:34:50
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
l = k #左边界
r = k #右边界
n = len(nums) #数组长度
res = 0 #最大可能分数
while 1 :
while r < n and nums[r] >= nums[k]:
r += 1 #向右寻找以nums[k]为最小值的好子数组
while l >= 0 and nums[l] >= nums[k]:
l -= 1 #向左寻找以nums[k]为最小值的好子数组
res = max(res, (r - l - 1) * nums[k]) #更新最大可能分数
if l < 0 and r == n: #遍历完数组，退出循环
break
if l >= 0 and r < n: #贪心，更新nums[k]为左右边界中的较大者
nums[k] = max(nums[l], nums[r])
elif l < 0: #左边已遍历完，更新为右边界
nums[k] = nums[r]
else: #右边已遍历完，更新左边界
nums[k] = nums[l]
return res
cpp 解法, 执行用时: 120 ms, 内存消耗: 88 MB, 提交时间: 2023-09-25 10:34:39
class Solution {
public:
// 单调栈
int maximumScore1(vector<int>& nums, int k) {
vector<int> mono_stack;
int ans = 0;
int n = nums.size();
auto update = [&](int i, int li, int ri) {
if (li <= k && k <= ri) {
ans = max(ans, nums[i] * (ri - li + 1));
}
};
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && nums[i] < nums[mono_stack.back()]) {
int idx = mono_stack.back();
mono_stack.pop_back();
int l_idx = (mono_stack.empty() ? 0 : mono_stack.back() + 1);
int r_idx = i - 1;
update(idx, l_idx, r_idx);
}
mono_stack.push_back(i);
}
while (!mono_stack.empty()) {
int idx = mono_stack.back();
mono_stack.pop_back();
int l_idx = (mono_stack.empty() ? 0 : mono_stack.back() + 1);
int r_idx = n - 1;
update(idx, l_idx, r_idx);
}
return ans;
}
// 贪心
int maximumScore2(vector<int>& nums, int k) {
int l = k, r = k, n = nums.size();
int ans = nums[k], mn = nums[k];
while (l > 0 || r < n - 1) {
if (l == 0) mn = min(mn, nums[++r]);
else if (r == n - 1) mn = min(mn, nums[--l]);
else {
if (nums[l - 1] > nums[r + 1])
mn = min(mn, nums[--l]);
else
mn = min(mn, nums[++r]);
}
ans = max(ans, mn * (r - l + 1));
}
return ans;
}
// 贪心 + 双指针
int maximumScore(vector<int>& nums, int k) {
int l = k, r = k, n = nums.size(), res = 0; //定义左右边界l r，最大可能分数res
while(1){
while(r < n && nums[r] >= nums[k]) r++; //向右寻找以nums[k]为最小值的好子数组
while(l >= 0 && nums[l] >= nums[k]) l--; //向左寻找以nums[k]为最小值的好子数组
res = max(res, (r - l - 1) * nums[k]); //更新最大可能分数
if(l < 0 && r == n) break; //遍历完数组，直接退出循环
if(l >= 0 && r < n) nums[k] = max(nums[l], nums[r]); //更新nums[k] 为左右边界中的较大者
else if(l < 0) nums[k] = nums[r]; //左边遍历完了，更新nums[k]为右边界
else nums[k] = nums[l]; //右边遍历完了，更新nums[k]为左边界
}
return res;
}
};
python3 解法, 执行用时: 460 ms, 内存消耗: 25.4 MB, 提交时间: 2023-09-25 10:32:32
'''
单调栈
'''
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
mono_stack = []
ans = 0
n = len(nums)
#
def update(i: int, li: int, ri: int):
if li <= k <= ri:
nonlocal ans
ans = max(ans, nums[i] * (ri - li + 1))
for i, num in enumerate(nums):
while mono_stack and nums[i] < nums[mono_stack[-1]]:
idx = mono_stack.pop()
l_idx = 0 if not mono_stack else mono_stack[-1] + 1
r_idx = i - 1
update(idx, l_idx, r_idx)
mono_stack.append(i)
while mono_stack:
idx = mono_stack.pop()
l_idx = 0 if not mono_stack else mono_stack[-1] + 1
r_idx = n - 1
update(idx, l_idx, r_idx)
return ans