原文鏈接：https://blog.csdn.net/qq_37964547/article/details/80701630
1、題目描述
請編寫一個程序，按升序?qū)＿M行排序，要求最多只能使用一個額外的棧存放臨時數(shù)據(jù)，但不得將元素復制到別的數(shù)據(jù)結(jié)構(gòu)中。
vector數(shù)組numbers中的第一個元素就是棧頂元素，升序排列，即棧頂元素最大
2、解題思路
看到這個題，因為可以申請一個棧用來存放臨時數(shù)據(jù)，所以我們可以這樣想：
由于棧先進后出的特性，先將原來棧中的數(shù)據(jù)存放到臨時數(shù)據(jù)棧中，并且保證臨時棧中的數(shù)據(jù)是降序排列的，這一過程完成之后，再將臨時數(shù)據(jù)棧中的元素依次push到返回棧中即可。
具體實現(xiàn)步驟：
（1）申請一個數(shù)據(jù)棧s用來存放numbers中的數(shù)據(jù)，再申請一個臨時棧tmp用來存放臨時數(shù)據(jù)
（2）比較s棧彈出的棧頂元素top與tmp的棧頂元素，并進行相應的操作，以確保tmp棧中的數(shù)據(jù)是降序的，具體比較過程如下：
當s棧不為空時：
條件 具體操作
若tmp棧為空或者top<=tmp.top（） 就將top元素push到tmp棧中
若tmp棧不為空并且top>tmp.top（） 將tmp中比top小的元素都push到s棧中，最后再將top元素push到tmp棧中
（3）此時tmp棧中的棧頂元素為最小值，將tmp棧中的元素依次彈出到s棧中，再將s棧中的元素依次彈出并保存到一個vector數(shù)組中。
操作演示圖：
3、代碼實現(xiàn)：
class TwoStacks {
public:
vector<int> twoStacksSort(vector<int> numbers) {
// write code here
int size=numbers.size();
stack<int>s;
stack<int>tmp;
vector<int> res;
for(int i=size-1;i>=0;i--)
s.push(numbers[i]);
while(!s.empty())
{
int top=s.top();
s.pop();
if(tmp.empty()||top<=tmp.top())
tmp.push(top);
else{
while(!tmp.empty()&&top>tmp.top())
{
s.push(tmp.top());
tmp.pop();
}
tmp.push(top);
}
}
while(!tmp.empty())
{
s.push(tmp.top());
tmp.pop();
}
while(!s.empty())
{
res.push_back(s.top());
s.pop();
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Shining-LY
關(guān)注
————————————————
版權(quán)聲明：本文為CSDN博主「Shining-LY」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/qq_37964547/article/details/80701630
