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;}
}