You are given an array of integers nums
(0-indexed) and an integer k
.
The score of a subarray (i, j)
is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)
. A good subarray is a subarray where i <= k <= j
.
Return the maximum possible score of a good subarray.
Example 1:
Input: nums = [1,4,3,7,4,5], k = 3 Output: 15 Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.
Example 2:
Input: nums = [5,5,4,5,4,1,1,1], k = 0 Output: 20 Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 2 * 104
0 <= k < nums.length
Solutions: Two Pointers
maintain a window [i, j], m = min(nums[i~j]), expend to the left if nums[i – 1] >= nums[j + 1], otherwise expend to the right.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int maximumScore(vector<int>& nums, int k) { const int n = nums.size(); int ans = 0; for (int i = k, j = k, m = nums[k];;) { ans = max(ans, m * (j - i + 1)); if (j - i + 1 == n) break; int l = i ? nums[i - 1] : -1; int r = j + 1 < n ? nums[j + 1] : -1; if (l >= r) m = min(m, nums[--i]); else m = min(m, nums[++j]); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment