|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。
-  
- 示例 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/validate-stack-sequences
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
- //模拟
- map<int, int>state;//记录当前元素在栈中的的状态,-1没有入栈, 0已经出栈, 1在栈中
- for(auto cha : pushed){
- state[cha] = -1;
- }
- int len = popped.size();
- int cur_push_position = -1;//当前待放入堆中的元素在pushed中的位置,之前位置的元素是已经放入堆中的
- int stack_top_position = -1;//当前堆顶在pushed中的坐标
- for(int i = 0; i < len; i++){
- int cur_pop_number = popped[i];
- if(state[cur_pop_number] == -1){
- while(pushed[++cur_push_position] != cur_pop_number){
- state[pushed[cur_push_position]] = 1;
- }
- }else if(stack_top_position < 0 || cur_pop_number == pushed[stack_top_position]){
- }else{
- return false;
- }
- state[cur_pop_number] = 0;
- stack_top_position = cur_push_position;
- while(--stack_top_position >= 0 && state[pushed[stack_top_position]] != 1);
- if(stack_top_position < 0){
- stack_top_position = -1;
- }
- }
- return true;
- }
- };
复制代码 |
|