[数据结构与算法]【LeetCode】tag—数组 119、121

119、杨辉三角II

利用 ArrayList<ArrayList<Integer>> A = new ArrayList<>();创建一个二维数组。
规律：在一行中，除了第一个数和最后一个数，第j个数等于上一行的第j个数加第j-1个数。

class Solution {
          public List<Integer> getRow(int rowIndex) {
              ArrayList<ArrayList<Integer>> A = new ArrayList<>();
              //最外层循环控制行数。i表示第i行。
              for (int i = 0; i < rowIndex + 1; i++) {
                  ArrayList<Integer> arrayList = new ArrayList<>();
                  //内层循环控制每行个数。
                  for (int j = 0; j <= i; j++) {
                      if (j == 0 || j == i) {
                          arrayList.add(1);
                      } else {
                          arrayList.add(A.get(i - 1).get(j - 1) + A.get(i - 1).get(j));
                      }
                  }
                  //得到一行的数之后再放入二维数组中。
                  A.add(arrayList);
              }
              return A.get(rowIndex);
          }
      }

121 买卖股票的最佳时机

该题运用两个For循环来求解会超出时间限制，所以这里只用一个for循环。

• 思路：假设在第i+1点卖出，那么只需要找到在[0,i]之间的最小值minprices即可，这样求出的差值即为最大利润，其中最大利润maxprices随着向后遍历而动态变化。

class Solution {
    public int maxProfit(int[] prices) {
        int minprices=Integer.MAX_VALUE;
        int maxprices=0;
        for(int i=0;i<prices.length-1;i++){
            if(prices[i]<minprices){
            //记录在i+1点卖出时，i+1点之前的最小值。
                minprices=prices[i];
            }
            //如果i+1点卖出的利润最高。
            if(prices[i+1]-minprices>maxprices){
            //就保存此时i+1点卖出的利润。
                maxprices=prices[i+1]-minprices;
            }
        }
        return maxprices;
    }
}