算法面试——栈与队列高频题：最小栈、滑动窗口最大值

栈和队列的面试题通常不是在考数据结构本身而是考如何用它们解决实际问题。一、最小栈classMinStack{privateStackIntegerdataStack;privateStackIntegerminStack;publicMinStack(){dataStacknewStack();minStacknewStack();}publicvoidpush(intval){dataStack.push(val);if(minStack.isEmpty()||valminStack.peek()){minStack.push(val);}}publicvoidpop(){if(dataStack.pop().equals(minStack.peek())){minStack.pop();}}publicinttop(){returndataStack.peek();}publicintgetMin(){returnminStack.peek();}}二、有效的括号publicbooleanisValid(Strings){StackCharacterstacknewStack();for(charc:s.toCharArray()){if(c(||c[||c{){stack.push(c);}else{if(stack.isEmpty())returnfalse;chartopstack.pop();if(c)top!()returnfalse;if(c]top![)returnfalse;if(c}top!{)returnfalse;}}returnstack.isEmpty();}三、滑动窗口最大值publicint[]maxSlidingWindow(int[]nums,intk){if(nums.length0)returnnewint[0];int[]resultnewint[nums.length-k1];DequeIntegerdequenewArrayDeque();for(inti0;inums.length;i){while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){deque.pollLast();}deque.offerLast(i);if(deque.peekFirst()i-k){deque.pollFirst();}if(ik-1){result[i-k1]nums[deque.peekFirst()];}}returnresult;} 觉得有用的话点赞 关注【张老师技术栈】吧