文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個整數數組 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 <= 10^5 1 <= nums[i] <= 2 * 10^4 0 <= k < nums.length

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-score-of-a-good-subarray
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 正反兩次單調棧，獲取以每個數字為最小值的區間 左右界限

class Solution { public:int maximumScore(vector<int>& nums, int k) {int n = nums.size();vector<int> right(n,-1), left(n,-1);stack<int> s;for(int i = n-1; i >= 0; i--){while(!s.empty() && nums[s.top()] >= nums[i])s.pop();//大于等于我的，我是最小的啦，刪除，接著往后找if(!s.empty())right[i] = s.top()-1;elseright[i] = n-1;s.push(i);}while(!s.empty()) s.pop();for(int i = 0; i < n; i++){while(!s.empty() && nums[s.top()] >= nums[i])s.pop();if(!s.empty())left[i] = s.top()+1;elseleft[i] = 0;s.push(i);}int maxScore = 0;for(int i = 0; i < n; i++)if(left[i] <= k && k <= right[i])maxScore = max(maxScore, nums[i]*(right[i]-left[i]+1));return maxScore;} };

288 ms 98.2 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1793. 好子数组的最大分数（单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。