作者推荐
题目
给你一个整数数组 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 <= 105
1 <= nums[i] <= 2 * 104
0 <= k < nums.length
分析
时间复杂度
O(n)。
步骤
一，寻找nums[i]的右边界，数组边界或从左向右第一个小于nums[i]的数。如果i1小于i2，且nums[i1] <= nums[i2]，则i1淘汰了i2，淘汰后:i降序，nums[i]升序。
二，寻找nums[i]的左边界，数组左边界或从右向左，第一个小于nums[i]的数。
三，左开右开区间(vLeft[i],vRight[i]) 就是以nums[i]为最小值的区间。如果k在这个区间，则更新返回值。
代码
核心代码
class Solution { public: int maximumScore(vector& nums, int k) { m_c = nums.size(); vector vRight(m_c, m_c); { vector vIndexs; for (int i = m_c-1 ; i >= 0 ; i-- ) { while (vIndexs.size() && (nums[vIndexs.back()] >= nums[i])) { vIndexs.pop_back(); } if (vIndexs.size()) { vRight[i] = vIndexs.back(); } vIndexs.emplace_back(i); } } vector vLeft(m_c, -1); { vector vIndexs; for (int i = 0; i < m_c; i++) { while (vIndexs.size() && (nums[vIndexs.back()] >= nums[i])) { vIndexs.pop_back(); } if (vIndexs.size()) { vLeft[i] = vIndexs.back(); } vIndexs.emplace_back(i); } } int iRet = 0; for (int i = 0; i < m_c; i++) { if ((k > vLeft[i]) && (k < vRight[i])) { iRet = max(iRet, nums[i] * (vRight[i] - vLeft[i] - 1)); std::cout << i << " nums[i]:" << nums[i] << " " << vLeft[i] << " " << vRight[i] <<std::endl; } } return iRet; } int m_c; }; 优化：寻找边界
循环一次
| 左边界 | 数组边界或小于nums[i] |
| 右边界 | 数组边界或小于等于nums[i] |
改变规则后：寻找左边界淘汰vIndexs时，说明：i是vIndexs.back()的第一个小于等于的数，也就是右边界。
题外话
解法一会造成重复，本题是求最大值，重复不会影响结果。求和就会有影响了。
比如：{1,1}
| 解法一 | 解法二 | |
| i=0 | {1,1} | {1} |
| i=1 | {1,1} | {1,1} |
拆开后：
| 解法一： | {1}，{1}，{1,1}，{1,1} |
| 解法二： | {1}，{1,1}，{1} |
代码
class Solution { public: int maximumScore(vector<int>& nums, int k) { m_c = nums.size(); vector<int> vRight(m_c, m_c); vector<int> vLeft(m_c, -1); vector<int> vIndexs; for (int i = 0; i < m_c; i++) { while (vIndexs.size() && (nums[vIndexs.back()] >= nums[i])) { vRight[vIndexs.back()] = i; vIndexs.pop_back(); } if (vIndexs.size()) { vLeft[i] = vIndexs.back(); } vIndexs.emplace_back(i); } int iRet = 0; for (int i = 0; i < m_c; i++) { if ((k > vLeft[i]) && (k < vRight[i])) { iRet = max(iRet, nums[i] * (vRight[i] - vLeft[i] - 1)); std::cout << i << " nums[i]:" << nums[i] << " " << vLeft[i] << " " << vRight[i] <<std::endl; } } return iRet; } int m_c; };
2023年3月旧代码
class Solution { public: int maximumScore(vector& nums, int k) { m_c = nums.size(); vector<std::pair<int, int>> staLeft,staRight; { for (int i = 0; i < k; i++) { while (staLeft.size() && (staLeft.back().first >= nums[i])) { staLeft.pop_back(); } staLeft.emplace_back(nums[i], i); } } { for (int i = nums.size() - 1; i > k; i–) { while (staRight.size() && (staRight.back().first >= nums[i])) { staRight.pop_back(); } staRight.emplace_back(nums[i], i); } } auto CmpFun = [](const std::pair<int, int>& p, int iCmp) {return p.first < iCmp; }; int iMaxRet = 0 ; for (int iValue = 1; iValue <= nums[k]; iValue++) { auto it = std::lower_bound(staLeft.begin(), staLeft.end(), iValue, CmpFun); int iLeft = (staLeft.begin() == it) ? -1 : (–it)->second; auto it2 = std::lower_bound(staRight.begin(), staRight.end(), iValue, CmpFun); int iRight = (staRight.begin() == it2) ? m_c : (–it2)->second; iMaxRet = max(iMaxRet, iValue* (iRight - iLeft - 1)); } return iMaxRet; } int m_c; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
