文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個整數數組 A，返回滿足下面條件的 非空、連續 子數組的數目：

子數組中，最左側的元素不大于其他元素。

示例 1： 輸入：[1,4,2,5,3] 輸出：11 解釋：有 11 個有效子數組，分別是：[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。示例 2： 輸入：[3,2,1] 輸出：3 解釋：有 3 個有效子數組，分別是：[3],[2],[1] 。示例 3： 輸入：[2,2,2] 輸出：6 解釋：有 6 個有效子數組，分別為是：[2],[2],[2],[2,2],[2,2],[2,2,2] 。提示： 1 <= A.length <= 50000 0 <= A[i] <= 100000

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

2. 解題

• 建立單調遞增的棧，存入元素的下標
• 當遇到遞減時，彈棧，以 s.top() 開頭， 結尾在 [s.top()，i-1]的 都是滿足的子數組

class Solution { public:int validSubarrays(vector<int>& nums) {stack<int> s;nums.push_back(-1); // 保證最后全部清空棧int count = 0;for(int i = 0; i < nums.size(); ++i){while(!s.empty() && nums[i] < nums[s.top()]){count += i-s.top();s.pop();}s.push(i);}return count;} };

160 ms 43.8 MB

---

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

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

總結

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

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