資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最大坡度
假設我們有一個整數陣列 A，坡度是一個元組 (i, j)，其中 i < j 且 A[i] <= A[j]。這種坡度的寬度為 j - i。我們必須找出 A 中坡度的最大寬度。如果不存在坡度，則返回 0。因此，如果輸入類似於 [6,0,8,2,1,5]，則輸出將是 4。此處，最大寬度坡度出現在 (i, j) = (1, 5)，其中 A[1] = 0，且 A[5] = 5
為解決此問題，我們將遵循以下步驟
建立一個數組 v，設定 n := 給定陣列的大小，設定 ret := 0
定義一個棧 st
對於 i 在 0 到 n – 1 範圍內的值
如果 st 為空或棧頂部元素 > A[i]，則將 i 插入 st
對於 i := n – 1 到 ret + 1 向下
當 st 不為空且棧頂部 <= A[i] 時
ret := ret 與 (i – 棧頂部) 中的最大值
從 st 中刪除
從 st 中刪除
讓我們看看以下實現，以獲得更好的理解
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
vector < pair <int, int> > v;
int n = A.size();
int ret = 0;
stack <int> st;
for(int i = 0; i < n; i++){
if(st.empty() || A[st.top()] > A[i]){
st.push(i);
}
}
for(int i = n - 1; i > ret; i--){
while(!st.empty() && A[st.top()] <= A[i]){
ret = max(ret, i - st.top());
st.pop();
}
}
return ret;
}
};
main(){
vector<int> v1 = {6,0,8,2,1,5};
Solution ob;
cout << (ob.maxWidthRamp(v1));
}輸入
[6,0,8,2,1,5]
輸出
4
更新日期：2020 年 4 月 30 日
331 次瀏覽
廣告