lintcode 中等题:

题目

买卖股票的最佳时机

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

样例

给出一个数组样例 [3,2,3,1,2], 返回 1

解题

通俗点说就是求 后面的数减去前面数所得结果的最大值,最后和0取最大值。

直接暴力,时间发杂度O(N2)

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        int Max = 0;
        if( prices == null || prices.length == 0)
            return 0;

        for(int i = 0;i< prices.length ;i++){
            for(int j = i;j< prices.length ;j++)
                Max = Math.max(Max, prices[j] - prices[i]);
        }
        return Max;
    }
}

Java Code

上面的程序又j==i的一项,不要对最后结果和0比较取最大值了。

那么问题来了,有没有更好的方法了?

分成两部分,前半部分的最小值  后半部分最大值,两者相减就是答案,这个貌似不好解。

在变量数组的时候,其前面的最小值比较求,当前节点可以当作最大值,这个假定的最大值 和之前求的最小值的差,也就当前节点卖出所获的收益,是局部最大值。

局部最大值的最大值就是整体最大值。

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        int result = 0;
        if( prices == null || prices.length == 0)
            return 0;
        int min = prices[0];
        for(int i = 1;i< prices.length ;i++){
            result = Math.max(result,prices[i] - min);
            min = Math.min(min,prices[i]);
        }
        return result;
    }
}

Java Code

总耗时: 1303 ms

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        if prices == None or len(prices) ==0:
            return 0
        Min = prices[0]
        res = 0
        for p in prices:
            res = max(res,p-Min)
            Min = min(Min,p)
        return res 

Python Code

总耗时: 218 ms

时间: 11-18

lintcode 中等题:的相关文章

lintcode 中等题:next permutation下一个排列

题目 下一个排列 给定一个整数数组来表示排列,找出其之后的一个排列. 样例 给出排列[1,3,2,3],其下一个排列是[1,3,3,2] 给出排列[4,3,2,1],其下一个排列是[1,2,3,4] 注意 排列中可能包含重复的整数 解题 和上一题求上一个排列应该很类似 1.对这个数,先从右到左找到递增序列的前一个位置,peakInd 2.若peakInd = -1 这个数直接逆序就是答案了 3.peakInd>= 0 peakInd这个位置的所,和 peakInd 到nums.size() -1

lintcode 中等题:maximum subarray difference 最大子数组差

题目 最大子数组差 给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大. 返回这个最大的差值. 样例 给出数组[1, 2, -3, 1],返回 6 注意 子数组最少包含一个数 挑战 时间复杂度为O(n),空间复杂度为O(n) 解题 刚做了数组中两个子数组和的最大值,这一题是求差,感觉上题的求解思想应该是可以用的 A B 分别是两个子数组的和,则: 所以 当A>B 的时候A越大越好 B越小越好 当A<B 的时候B越大越好 A越小越好

lintcode 中等题:continuous subarray sum 联系子数组之和

题目 连续子数组求和 给定一个整数数组,请找出一个连续子数组,使得该子数组的和最大.输出答案时,请分别返回第一个数字和最后一个数字的值.(如果两个相同的答案,请返回其中任意一个) 样例 给定 [-3, 1, 3, -3, 4], 返回[1,4]. 解题 法一:直接暴力,时间复杂度O(N2),时间超时 public class Solution { /** * @param A an integer array * @return A list of integers includes the i

lintcode 中等题:maximum subarray最大子数组II

题目 最大子数组 II 给定一个整数数组,找出两个不重叠子数组使得它们的和最大. 每个子数组的数字在数组中的位置应该是连续的. 返回最大的和. 您在真实的面试中是否遇到过这个题? Yes 样例 给出数组[1, 3, -1, 2, -1, 2],这两个子数组分别为[1, 3]和[2, -1, 2]或者[1, 3, -1, 2]和[2],它们的最大和都是7 注意 子数组最少包含一个数 挑战 要求时间复杂度为O(n) 解题 最大子数组I 这个题目是求一个数组中一个最大子数组的和,而本题目是求数组中的前

lintcode 中等题: Implement Trie

题目 Implement Trie Implement a trie with insert, search, and startsWith methods. 样例 注意 You may assume that all inputs are consist of lowercase letters a-z. 解题 Trie,字典树,又称单词查找树.前缀树,是一种哈希树的变种.应用于字符串的统计与排序,经常被搜索引擎系统用于文本词频统计. 性质: 1.根节点不包含字符,除根节点外的每一个节点都只包

lintcode 中等题: 3 Sum II 三数之和II

题目 三数之和 II 给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组,返回这三个数的和. 样例 例如S = [-1, 2, 1, -4] and target = 1.  和最接近1的三元组是 -1 + 2 + 1 = 2. 注意 只需要返回三元组之和,无需返回三元组本身 解题 和上一题差不多,程序也只是稍微修改了 public class Solution { /** * @param numbers: Give an array numbers of n integ

lintcode 中等题:sort letters by case字符大小写排序

题目 字符大小写排序 给定一个只包含字母的字符串,按照先小写字母后大写字母的顺序进行排序. 您在真实的面试中是否遇到过这个题? Yes 样例 给出"abAcD",一个可能的答案为"acbAD" 注意 小写字母或者大写字母他们之间不一定要保持在原始字符串中的相对位置. 挑战 在原地扫描一遍完成 解题 这个题目很简单,前面刚做一个把大于某个数之和的排在后面,快速排序的思想 public class Solution { /** *@param chars: The le

lintcode 中等题:N Queens II N皇后问题 II

题目: N皇后问题 II 根据n皇后问题,现在返回n皇后不同的解决方案的数量而不是具体的放置布局. 样例 比如n=4,存在2种解决方案 解题: 和上一题差不多,这里只是求数量,这个题目定义全局变量,递归的时候才能保存结果,参考程序 java程序: class Solution { /** * Calculate the total number of distinct N-Queen solutions. * @param n: The number of queens. * @return:

lintcode 中等题:binary tree level order traversal ii 二叉树的层次遍历II

题目 二叉树的层次遍历 II 给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历) 样例 给出一棵二叉树 {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 按照从下往上的层次遍历为: [ [15,7], [9,20], [3] ] 解题 和上一题的答案反过来 直接每次在list中第一个位置加入当前层结点 /** * Definition of TreeNode: * public class TreeNode { *

lintcode 中等题:kth-largest-element 第k大元素

题目 第k大元素 在数组中找到第k大的元素 样例 给出数组[9,3,2,4,8],第三大的元素是4 给出数组 [1,2,3,4,5],第一大的元素是5,第二大的元素是4,第三大的元素是3,以此类推 注意 你可以交换数组中的元素的位置 挑战 要求时间复杂度为O(n),空间复杂度为O(1) 解题 理论快速排序的思想,每次都减半,这个时间复杂度也是O(N),至于为什么就不知道了 class Solution { /* * @param k : description of k * @param num