byu_rself

LC.P303[区域和检索-数组不可变] 方法一：前缀和12345678910111213141516171819202122class NumArray { int[] sum; public NumArray(int[] nums) { int n = nums.length; sum = new int[n + 1]; for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { return sum[right + 1] - sum[left]; }}/** * Your NumArray object will be instantiated and called as such: * NumArray ...

LC.P1090[受标签影响的最大值] 方法一：贪心+排序+哈希表123456789101112131415161718192021class Solution { public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) { int n = values.length; int[][] index = new int[n][2]; for (int i = 0; i < n; ++i) { index[i] = new int[]{values[i], labels[i]}; } Arrays.sort(index, (a, b) -> b[0] - a[0]); Map<Integer, Integer> map = new HashMap<>(); ...

LC.P739[每日温度] 方法一：单调栈123456789101112131415class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; Deque<Integer> stack = new ArrayDeque<>(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int index = stack.pop(); ans[index] = i - index; } ...

LC.P1080[根到叶路径上的不足节点] 方法一：DFS123456789101112131415161718192021222324252627282930/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public Tree ...

LC.P795[区间子数组个数] 方法一：单调栈123456789101112131415161718192021222324252627282930313233class Solution { public int numSubarrayBoundedMax(int[] nums, int left, int right) { int n = nums.length; int[] l = new int[n], r = new int[n]; Arrays.fill(l, -1); Arrays.fill(r, n); Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { // 求nums[i]的左侧第一个大于该元素的下标l[i] int num = nums[i]; while ...

LC.P2104[子数组范围和] 方法一：暴力123456789101112131415class Solution { public long subArrayRanges(int[] nums) { long ans = 0; int n = nums.length; for (int i = 0; i < n; ++i) { int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for (int j = i; j < n; ++j) { min = Math.min(min, nums[j]); max = Math.max(max, nums[j]); ans += max - min; } } return ans; ...

LCP.33[蓄水] 方法一：贪心123456789101112131415class Solution { public int storeWater(int[] bucket, int[] vat) { int max = Arrays.stream(vat).max().getAsInt(); if (max == 0) return 0; int n = vat.length, ans = Integer.MAX_VALUE; for (int i = 1; i <= max; ++i) { // 蓄水次数 int j = 0; // 升级次数 for (int k = 0; k < n; ++k) { j += Math.max(0, (vat[k] + i - 1) / i - bucket[k]); } ans = Math.min( ...

LC.P1373[二叉搜索子树的最大键值和] 方法一：DFS123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution &# ...

LC.P1206[设计跳表] 方法一：构造123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110class Skiplist { private static final int MAX_LEVEL = 32; private static final double SKIPLIST_P = 0.25; private Node head; private int curLevel; public Skiplist() { this.head = new Node(-1, MAX_LEVEL); this.curLevel = ...

LC.P84[柱状图中最大的矩形] 方法一：单调栈12345678910111213141516171819202122232425class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length, ans = 0; int[] l = new int[n], r = new int[n]; Arrays.fill(l, -1); Arrays.fill(r, n); Deque<Integer> stack = new ArrayDeque<>(); // 确定右边界 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) r[stack.p ...