150. 逆波兰表达式求值

答案：

class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
for (String s : tokens) {
if ("+".equals(s)) {
// leetcode 内置jdk的问题，不能使用==判断字符串是否相等
stack.push(stack.pop() + stack.pop());
// 注意 - 和/ 需要特殊处理
} else if ("-".equals(s)) {
stack.push(-stack.pop() + stack.pop());
} else if ("*".equals(s)) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(s)) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}

注意：

• 首先是对String数组的遍历，有很多种方法，具体可见： Java8的String数组遍历方式，但是如果用for便利的话，不好将数组中的每个字符串String和+，-，*，/符号进行对比。
• 对于除了String类型的数组外，每种数组类型都有length属性，而String类型的变量，拥有的是length方法，在String数组中，仍然有具有了length属性，详情可见：关于数组的length和String的length
• 对于减法和除法，需要特殊处理，分清楚出栈元素哪个在前哪个在后。
• x.valueOf(String s)可以将字符串s转换为x类型，而String类型也有valueOf的方法，是将参数中的类型转换为String类型
• 对于valueOf方法，如果替换成parseInt方法，仍然可以通过，两者的作用类似，具体区别可见： 探讨 Java 中 valueOf 和 parseInt 的区别

239. 滑动窗口最大值

思路

举例
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解释过程中队列中都是具体的值，方便理解，具体见代码。
初始状态：L=R=0,队列:{ }
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]

因为在i=0，1情况时，R虽然在增长，但此时并不用让L也增长，因为L就算是0，也能使整个窗口的大小满足k=3，但是后面 i=2~7的过程中，因为R一直不断右移，如果此时还不再移动L，就不能满足窗口大小是k的要求了，要一直让窗口为k

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if( nums.length < k) return nums;
// 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
LinkedList<Integer> queue = new LinkedList();
// 结果数组
int[] result = new int[nums.length-k+1];
// 遍历nums数组
for(int i = 0;i < nums.length;i++){
// 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
queue.pollLast();
}
// 添加当前值对应的数组下标
queue.addLast(i);
// 判断当前队列中队首的值是否有效
if(queue.peek() <= i-k){
queue.poll();
}
// 当窗口长度为k时 保存当前窗口中最大值
if(i+1 >= k){
result[i+1-k] = nums[queue.peek()];
}
}
return result;
}
}

最后

以上就是光亮雪糕为你收集整理的代码随想录第十五天（150、239）150. 逆波兰表达式求值239. 滑动窗口最大值的全部内容，希望文章能够帮你解决代码随想录第十五天（150、239）150. 逆波兰表达式求值239. 滑动窗口最大值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。