Hot100

Hot100

贪心算法

• 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

  你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

  返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

  class Solution {
      public int maxProfit(int[] prices) {
          if(prices.length==0){
              return 0;
          }
          int max=0,len=prices.length;
          int pre=prices[0];
          for(int p:prices){
              if(p<pre){
                  pre=p;
              }
              max=Math.max(max,p-pre);
          }
          return max;
      }
  }
  

• 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

  判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false

  class Solution {
      public boolean canJump(int[] nums) {
          int n = nums.length;
          int farthest = 0;
          for (int i = 0; i < n - 1; i++) {
              // 不断计算能跳到的最远距离
              farthest = Math.max(farthest, i + nums[i]);
              // 可能碰到了 0，卡住跳不动了
              if (farthest <= i) {
                  return false;
              }
          }
          return farthest >= n - 1;
      }
  }