我胡汉三又回来刷题了! [LeetCode/Lintcode 题解:山脉序列中的最大值]

国庆假期结束,来收收心~

给 n 个整数的山脉数组,即先增后减的序列,找到山顶(最大值)

  • 数组严格递增,严格递减

点此在线做题

例 1:

输入: nums = [1, 2, 4, 8, 6, 3] 
输出: 8

例 2:

输入: nums = [10, 9, 8, 7], 
输出: 10

算法:二分

算法思路

  • 由于本题数据是具有部分单调性,我们可以考虑用二分法来解决
  • 并且本题保证数组严格递增或严格递减,所以相邻两个数必不相等
  • 我们可以通过 a[mid]和 a[mid+1]的大小关系来判断 mid 是在左侧还是右侧

代码思路

  1. 设置左边界等于 0,右边界等于 numsLen – 1
  2. 对于 mid 所指向的数,若 nums[mid] > nums[mid + 1]则表示 mid 指向的数在最大值右侧或最大值,那么 right = mid,否则 left = mid
  3. 不断重复 2 直到 left + 1 == right 退出
  4. left 和 right 指向的数中较大的一个即最大值,将其返回

复杂度分析

N 表示数组 nums 长度

  • 空间复杂度:O(N)
  • 时间复杂度:O(logN)
public class Solution {
    /**
     * @param nums: a mountain sequence which increase firstly and then decrease
     * @return: then mountain top
     */

    public int mountainSequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return Math.max(nums[left], nums[right]);
    }
}

不知道有没有人组个刷题群,互相监督刷题的

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注