資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律C++ 中有效子陣列的數量
假設我們有一個整數陣列 A，我們需要找到滿足以下條件的非空連續子陣列的數量：子陣列的最左元素不超過子陣列中的其他元素。
因此，如果輸入類似於 [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]。
為了解決這個問題，我們將遵循以下步驟 -
ret := 0
n := nums 的大小
定義一個棧 st
初始化 i := 0，當 i < nums 的大小，更新（i 增加 1），執行 -
x := nums[i]
當 (st 不為空且 x < st 的棧頂元素) 時，執行 -
從 st 中刪除元素
將 x 插入 st
ret := st 的大小 + ret
返回 ret
讓我們看看下面的實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int validSubarrays(vector<int>& nums) {
int ret = 0;
int n = nums.size();
stack <int> st;
for(int i = 0; i < nums.size(); i++){
int x = nums[i];
while(!st.empty() && x < st.top()) st.pop();
st.push(x);
ret += st.size();
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,4,2,5,3};
cout << (ob.validSubarrays(v));
}輸入
{1,4,2,5,3}輸出
11
更新於: 2020-07-11
388 次瀏覽
廣告