您的位置: 首页  >  IT文章  >  侧滑窗口最大值相关题目

侧滑窗口最大值相关题目

分类: IT文章 • 2025-01-10 11:45:08

最大树

给出一个没有重复的整数数组，在此数组上建立最大树的定义如下：

  • 根是数组中最大的数
  • 左子树和右子树元素分别是被父节点元素切分开的子数组中的最大值

利用给定的数组构造最大树。

思路：

对于元素cur,只需求得cur的左边的第一个比它大的数和右边的第一个比它大的数,把cur挂在这两个数中的较小的一个上。最后就一定能够得到一个这样的Max_Tree。

首先需要证明不会出现一个森林。

因为整个数组中元素各不相同，所以按照我们的规则，有且只有一个元素不能挂到其他元素上，所以结果一定构成一棵树，不会是森林。

其次证明都是二叉的，不会出现多余两个的儿子。

我们的规则是压栈的时候，如果当前元素比栈顶元素大，那么就弹出栈中的元素，直到栈为空或者栈顶元素比当前元素大。所以，

我们需要证明任意一个元素最多有一个儿子，可以证明任何一个元素最多有过一个右儿子。

a... b 假设b是a的右儿子，那么a是b的左边第一个比b大的数，a到b的数一定比b小，只有b才有可能为其父亲，b右边的数也只有b才有可能为其父亲。

所以a的单边最多有一个儿子。

 1  public TreeNode maxTree(int[] A) {
 2         // write your code here
 3         if (A == null || A.length == 0) {
 4             return null;
 5         }
 6         Stack<Integer> stack = new Stack<Integer>();
 7         HashMap<Integer,Integer> lessBigMap = new HashMap<Integer,Integer>();
 8         for (int i = 0; i < A.length; i++) {
 9             while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
10                 popAndSetMap(stack,lessBigMap,A,i);
11             }
12             stack.push(i);
13         }
14         while (!stack.isEmpty()) {
15             popAndSetMap(stack, lessBigMap, A, null);
16         }
17         TreeNode[] nodes = new TreeNode[A.length];
18         for (int i = 0; i < A.length; i++) {
19             nodes[i] = new TreeNode(A[i]);
20         }
21         TreeNode head = null;
22         for (Map.Entry<Integer, Integer> entry : lessBigMap.entrySet()) {
23            Integer son = entry.getKey();
24            Integer father = entry.getValue();
25            if (father != null) {
26                if (father > son) {
27                    nodes[father].left = nodes[son];
28                }
29                else {
30                    nodes[father].right = nodes[son];
31                }
32            }
33            else {
34                head = nodes[son];
35            }
36         }
37         return head;
38     }
39     public void popAndSetMap(Stack<Integer> stack, Map<Integer,Integer> map, int[] A, Integer r) {
40         int mid = stack.pop();
41         if (r != null && !stack.isEmpty()) {
42             map.put(mid, A[r] < A[stack.peek()] ? r:stack.peek());
43         }
44         else if (!stack.isEmpty()) {
45             map.put(mid, stack.peek());
46         }
47         else {
48            map.put(mid, r);
49         }
50     }
View Code

侧滑窗口最大值函数

给你一个数组和一个窗口大小k，要求窗口从数组开始滑动，求解各个窗口的最大值

  1. 使用一个双端队列，遍历数组，如果遇到的数比大于等于队列末尾的数，那么就弹出队列中的数，知道队列末尾大于当前数或者队列为空，然后把当前数加到队列中去。
  2. 检查队列开始的数是否有效，如果无效则应该弹出队列开头的数。
  3. 从i大于等于窗口时,队列首部就是以当前数为最右侧的窗口的最大值
 1 public int[] maxSlidingWindow(int[] nums, int k) {
 2      if(nums==null||k<1||nums.length<k)
 3          return new int[0];
 4      int len=nums.length;
 5      int[] res=new int[len-k+1];
 6      LinkedList<Integer> queue=new LinkedList<Integer>();
 7      int index=0;
 8      for(int i=0;i<len;i++){
 9          int cur=nums[i];
10          while(!queue.isEmpty()&&nums[queue.peekLast()]<=cur){
11              queue.pollLast();
12          }
13          queue.addLast(i);
14          if(i-k==queue.peekFirst())
15              queue.pollFirst();
16          if(i>=k-1){
17              res[index++]=nums[queue.peekFirst()];
18          }
19      }
20      return res;
21  }
View Code

最大值减去最小值小于或等于num的子数组数量

这是侧滑窗口最大值的延伸题目。有了侧滑窗口最大值和最小值，那么我们当然可以得到这个窗口满不满足条件。另外，本题还有一个关键点是假如侧滑窗口的左边界不动，右边界动只可能会让区间的最大最小值差值增大，左边界右移只会让区间的最大值最小值差值减小。所以，算法步骤为：

首先，R右移，知道左右的差值不满足条件，这是的左右差值为以left开始的满足条件的子数组数量。

然后，R此时再往右移已经肯定不行。此时L右移，肯定是可以的。然后此时求以新的left开始的数量。移动的过程中使用两个双端队列分别记录最大值和最小值。

 1 public static int getNum(int[] arr, int num) {
 2         LinkedList<Integer> qmin = new LinkedList<Integer>();
 3         LinkedList<Integer> qmax = new LinkedList<Integer>();
 4         int left = 0;
 5         int right = 0;
 6         int res = 0;
 7         while (left < arr.length) {
 8             while (right < arr.length) {
 9                 while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[right]) {
10                     qmin.pollLast();
11                 }
12                 qmin.addLast(right);
13                 while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[right]) {
14                     qmax.pollLast();
15                 }
16                 qmax.addLast(right);
17                 if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
18                     break;
19                 }
20                 //注意这上下两句顺序不可以颠倒
21                 right++;
22             }
23             if (left == qmin.peekFirst()) {
24                 qmin.pollFirst();
25             }
26             if (left == qmax.peekFirst()) {
27                 qmax.pollFirst();
28             }
29             res += right - left;//right位置已经不满足，所以不加1，left++再进来还是这个right
30             left++;
31         }
32         return res;
33     }
View Code

相关推荐