该题首先确定何为字典序最大的序列,即输出看成一个数字串,数字最大的哪一种。 我们先将所有输入放入到一个vector数组中去,然后遍历数组。 第一次肯定是直接入栈,一直到N,然后我们得确定N后的数组和栈的最后位置st.top(),哪一个更大。为了确定数组后面元素最大的位置,我写了一个maxIndex函数来返回最大位置下标。 然后,如果是st.top()和后续数组最大值的比较,如果后面的比较大,就一直入栈到那个最大的位置。 如果是st.top()比较大就一直出栈到st.toop()小于后续数组最大值,然后在入栈到那一个最大位置。 最后小tips:1.记得判断栈是否为空 2.遍历完后,记得弹出栈
#include<vector>
#include<stack>
using namespace std;
int maxIndex(const vector<int>&array, int index, int size) {
int max = array[index];
int back = index;
for (int i = index; i < size; i++) {
if (array[i] > max) {
max = array[i];
back = i;
}
}
return back;
}//获取未遍历完的数组中最大值的下标
int main() {
vector<int>array;
stack<int>st;
int size;
cin >> size;
for (int i = 0; i < size; i++) {
int temp;
cin >> temp;
array.push_back(temp);
}//将数据存入数组
for (int i = 0; i < size; i++) {
int temp = maxIndex(array, i, size);
if (st.empty()) {
while (i < temp) {
st.push(array[i]);
i++;
}
cout << array[temp] << " ";
}
else {
if (st.top() > array[temp]) {
while (!st.empty()&&st.top() > array[temp]) {
cout << st.top() << " ";
st.pop();
}
while (i < temp) {
st.push(array[i]);
i++;
}
cout << array[temp] << " ";
}
else {
while (i < temp) {
st.push(array[i]);
i++;
}
cout << array[temp] << " ";
}
}
}
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
}
刚刚学,肯定不是特别好,别喷,欢迎提出优化建议。