字节题目5

739. 每日温度

• 单调栈：遇到比自己高的弹出
  • 一个记录还没有遇到比自己高的温度的温度
  • 一个记录温度栈中温度的位置
  • 定义一个数组，存储结果

    class Solution {
    public int[] dailyTemperatures(int[] T) {
       Stack<Integer> temp = new Stack(); // 存放未确定的温度
       Stack<Integer> pos = new Stack(); // 存放未确定温度的位置
       int index = 0;
       int len = T.length;
       int[] res = new int[len]; // 存放结果
       while(index<len) {
           // 当前温度栈中已经遇到比自己高德温度了，可以弹出
           while(!temp.isEmpty() && temp.peek()<T[index]) {
               temp.pop();
               int p = pos.pop();
               res[p] = index-p;
           }            
           temp.push(T[index]); // 加入新的温度
           pos.push(index); //记录新温度的位置
           index++;
       }
       while(!pos.isEmpty()) {
           res[pos.pop()] = 0; // 当前栈中的温度都没有遇到比自己温度高的温度
       }
       return res;
    }
    }

    113. 路径总和 II

    

    class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
       dfs(root, 0, sum);
       return res;
    }
    public void dfs(TreeNode root, int num, int sum){
       if(root == null) return;
       num += root.val;
       list.add(root.val);
       if(num == sum && root.left == null && root.right == null) res.add(new ArrayList(list));
       dfs(root.left, num, sum);
       dfs(root.right, num, sum);
       list.remove(list.size() - 1);
    }
    }

    48. 旋转图像

    
    

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

215. 数组中的第K个最大元素

快速排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums,0,nums.length-1,nums.length-k);
    }
    public int find(int[] nums,int start,int end,int k) {
        if(start==end)
            return nums[start];
        int f = nums[start];
        int l = start;
        int r = end;
        while(l<r) {
            while(l<r && nums[r]>=f)
                r--;
            while(l<r && nums[l]<=f)
                l++;
            if(l<r) {
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
            }
        }
        nums[start] = nums[l];
        nums[l] = f;
        if(l==k) {
            return f;
        } else if(l>k) {
            return find(nums,start,l-1,k);
        } else {
            return find(nums,l+1,end,k);
        }
    }
}

230. 二叉搜索树中第K小的元素

• 中序遍历

  class Solution {
    public int kthSmallest(TreeNode root, int k) {
        return find(root,k);
    }
    int find(TreeNode root,int k) {
        Stack<TreeNode> stack = new Stack();
        TreeNode now = root;
        while(!stack.isEmpty() || root!=null) {
            while(now!=null) {
                stack.push(now);
                now=now.left;
            }
            now = stack.pop();
            k--;
            if(k==0)
                return now.val;
            now = now.right;
        }
        return -1;
    }
  }

  84. 柱状图中最大的矩形

  

• 计算出当前节点的左边界

• 计算出当前节点的右边界

  class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] L = new int[len];
        int[] R = new int[len];
        Stack<Integer> stackL = new Stack();
        Stack<Integer> stackR = new Stack();
        stackL.push(-1);
        for(int i = 0; i < heights.length ; i++) {
            while(stackL.peek()!= -1 && heights[stackL.peek()]>=heights[i]) {
                stackL.pop();
            }
            L[i] = stackL.peek();
            stackL.push(i);
        }
        stackR.push(len);
        for(int i = len-1;i>=0;i--) {
            while(stackR.peek()!=len && heights[stackR.peek()]>=heights[i]) {
                stackR.pop();
            }
            R[i] = stackR.peek();
            stackR.push(i);
        }
        // System.out.println(Arrays.toString(L));
        // System.out.println(Arrays.toString(R));
        int max = 0;
        for(int i = 0 ;i < len;i++) {
            max = Math.max(max,(R[i]-L[i]-1)*heights[i]);
        }
        return max;
    }
  }