[LintCode] Interval Minimum Number

taowen 发布于2019-08-14 16:23 / 525人阅读

摘要：这道题目是筛选出数组中的最小值，存入新数组。因此，联想到和系列的题目，对于的处理，使用线段树是非常有效的方法。之前我们创建的线段树，有和两个。参照这个参数，可以考虑在这道题增加一个的参数，代表每个结点的最小值。

Problem

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(1,2),(0,4),(2,4)], return [2,1,5]

Challenge

O(logN) time for each query

Note

这道题目是筛选出Interval数组中的最小值，存入新数组。因此，联想到Segment Tree Build和Segment Tree Query系列的题目，对于Interval的处理，使用线段树是非常有效的方法。之前我们创建的线段树，有max和count两个properties。参照max这个参数，可以考虑在这道题增加一个min的参数，代表每个结点的最小值。
详细思路见code。

Solution

public class Solution {
    public ArrayList intervalMinNumber(int[] A, 
                                                ArrayList queries) {
        ArrayList res = new ArrayList();
        if (A == null || queries == null) return res;
        MinTreeNode root = buildTree(A, 0, A.length-1);
        for (Interval i: queries) {
            res.add(getMin(root, i.start, i.end));
        }
        return res;
    }
    //创建新的树结构MinTreeNode
    public class MinTreeNode {
        int start, end, min;
        MinTreeNode left, right;
        public MinTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public MinTreeNode(int start, int end, int min) {
            this(start, end);
            this.min = min;
        }
    }
    //创建新的MinTreeNode
    public MinTreeNode buildTree(int[] A, int start, int end) {
        if (start > end) return null;
        //下面四行语句是recursion的主体
        if (start == end) return new MinTreeNode(start, start, A[start]);
        MinTreeNode root = new MinTreeNode(start, end);
        root.left = buildTree(A, start, (start+end)/2);
        root.right = buildTree(A, (start+end)/2+1, end);
        //下面三行语句设置每个结点的min值
        if (root.left == null) root.min = root.right.min;
        else if (root.right == null) root.min = root.left.min;
        else root.min = Math.min(root.left.min, root.right.min);
        return root;
    }
    //获得最小值min的子程序
    public int getMin(MinTreeNode root, int start, int end) {
        //空集和越界情况
        if (root == null || root.end < start || root.start > end) {
            return Integer.MAX_VALUE;
        }
        //最底层条件结构
        if (root.start == root.end || (start <= root.start && end >= root.end)) {
            return root.min;
        }
        //递归
        return Math.min(getMin(root.left, start, end), getMin(root.right, start, end));
    }
}

云服务器 GPU云服务器 Interval Minimum LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66195.html

[LintCode] Minimum Adjustment Cost [Undone]

Problem Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target. If the array before adjustment is A, the array after ...

Aomine 2019-08-14 15:29 评论0 收藏0
[LintCode] Segment Tree Query I & Segment Tree

摘要：题目是要查询到这个区间内某一点的。值是从最底层的子节点值里取最大值。因此，不用太复杂，递归就可以了。与所不同的是，对所给区间内的元素个数求和，而非筛选。这样就会出现的情况，视作本身处理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

vibiu 2019-08-14 16:22 评论0 收藏0
[LintCode/LeetCode] Integer Replacement

Problem Given a positive integer n and you can do operations as follow: 1.If n is even, replace n with n/2.2.If n is odd, you can replace n with either n + 1 or n - 1. What is the minimum number of re...

fyber 2019-08-16 12:44 评论0 收藏0
[LintCode] Interval Sum

摘要：很简单的题目，不过要达到的时间，只能用前缀和的方法来做。法前缀和法推荐 Problem Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each...

kelvinlee 2019-08-14 16:23 评论0 收藏0
[LintCode/LeetCode] Triangle

摘要：第一种方法是很早之前写的，先对三角形两条斜边赋值，和分别等于两条斜边上一个点的和与当前点的和。然后套用动规公式进行横纵坐标的循环计算所有点的，再遍历最后一行的，找到最小值即可。 Problem Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen...

刘德刚 2019-08-14 15:28 评论0 收藏0