|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-5-8 18:02 编辑
题目描述:
- 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
-  
- 示例 1:
- 输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
- 输出:true
- 解释:我们可以按以下顺序执行:
- push(1), push(2), push(3), push(4), pop() -> 4,
- push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
- 示例 2:
- 输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
- 输出:false
- 解释:1 不能在 2 之前弹出。
-  
- 提示:
- 0 <= pushed.length == popped.length <= 1000
- 0 <= pushed[i], popped[i] < 1000
- pushed 是 popped 的排列。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- #include <iostream>
- #include <stack>
- #include <vector>
- using namespace std;
- bool solution(vector<int>& pushed, vector<int>& popped){
- if(pushed.size() == 0) return true;
- stack<int> temp;
- temp.push(pushed[0]);
- int i = 0;
- int j = 1;
- while(!temp.empty()){
- if(j >= pushed.size() && i >= popped.size()) break;
- if(temp.top() == popped[i]){
- temp.pop();
- if(temp.empty() && j <pushed.size()){
- temp.push(pushed[j]);
- j++;
- }
- i++;
- continue;
- }
- if(temp.top() != popped[i]){
- if(j < pushed.size()){
- temp.push(pushed[j]);
- j++;
- }
- else{
- break;
- }
- }
- }
- return temp.empty();
-
- }
- int main(void){
- vector<int> pushed, popped;
- int number1, number2;
- while(cin >> number1){
- pushed.push_back(number1);
- }
- cin.clear();
- while(cin >> number2){
- popped.push_back(number2);
- }
-
- bool res = solution(pushed, popped);
- cout << res << endl;
- return 0;
- }
-
复制代码
注意事项:
1.边界确定。
2.参考链接:https://leetcode-cn.com/problems ... ion/tan-xin-by-z1m/ |
|