資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的迴圈陣列的下一個較大元素
假設我們有一個迴圈陣列（最後一個元素的下一個元素是該陣列的第一個元素），我們必須顯示每個元素的下一個較大數字。此處的某個數 x 的下一個較大數字是在陣列中按遍歷順序緊隨其後的第一個較大數字，這意味著我們可以迴圈搜尋以查詢其下一個較大數字。如果不存在，則為 -1。因此，如果數字為 [1, 2, 1, 3, 2, 1]，則輸出將為：[2,3,3,-1,3,2]
為了解決這個問題，我們將遵循以下步驟 -
- n := 陣列大小
- 定義一個名為 res 的大小為 n 的陣列，並用 -1 填充它，定義一個棧 st
- 對於 i 從 0 到 2n
- index := i mod n，x := nums[index]
- 當 st 非空且 nums[棧頂] < x
- res[棧頂] := x
- 刪除棧頂元素
- 將 index 插入棧
- 返回 res
示例 (C++)
讓我們看一下以下實現，以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector <int> res(n, - 1);
stack <int> st;
for(int i = 0; i < 2 * n; i++){
int idx = i % n;
int x = nums[idx];
while(!st.empty() && nums[st.top()] < x){
res[st.top()] = x;
st.pop();
}
st.push(idx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,1};
print_vector(ob.nextGreaterElements(v));
}輸入
[1,2,1,3,2,1]
輸出
[2,3,3,-1,3,2]
更新於: 2020 年 4 月 29 日
185 次觀看
廣告