# LeetCode初级算法题：子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零

LeetCode初级算法题：子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零java多种解法

## 1 子数组最大平均数

6 2 7 5 8 4 3 1

6 2 7 5 8 4 3 1

### 解题思路与代码

    public double findMaxAverage(int[] nums, int k) {
int sum = 0;
int n = nums.length;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
for (int i = k; i < n; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return 1.0 * maxSum / k;
}


## 2 二叉树的最小深度

### 解题思路与代码

#### 解法一：深度优先

 public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}

• 时间复杂度：O(N)
• 空间复杂度：O(logN) 取决于树的高度

#### 解法二：广度优先

    class QueueNode {
TreeNode node;
int depth;
public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}

}
return 0;
}

• 时间复杂度：O(N)
• 空间复杂度：O(N)

## 3 最长连续递增序列

### 题目描述

#### 贪心算法

    public static int findLength(int[] nums) {
int ans = 0;
int start = 0;
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] <= nums[i - 1]) {
start = i;
}
ans = Math.max(ans, i - start + 1);
}
return ans;
}


## 4 柠檬水找零

### 解题思路与代码

#### 贪心算法

    public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) {
five++;
} else if (bill == 10) {
if (five == 0) {
return false;
}
five--;
ten++;
} else {
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}


|
3天前
|

35 19
|
18天前
|

38 1
|
6天前
|

24 1
|
1月前
|

LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
34 6
|
1月前
|

LeetCode经典算法题：打家劫舍java详解
LeetCode经典算法题：打家劫舍java详解
38 2
|
1月前
|

LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
34 1
|
1月前
|

LeetCode经典算法题：预测赢家+香槟塔java解法
LeetCode经典算法题：预测赢家+香槟塔java解法
32 1
|
21天前
|

【初阶数据结构篇】二叉树算法题

12 0
|
26天前
|

【算法】贪心算法——柠檬水找零
【算法】贪心算法——柠檬水找零
23 0
|
26天前
|

【算法】栈算法——栈的压入、弹出序列
【算法】栈算法——栈的压入、弹出序列
10 0