数组、链表、跳表、栈、队列、优先级队列、双端队列

一、第一周学习笔记

（一）数组

（二）链表

（三）跳表

（四）栈

（五）队列

（六）优先级队列

（七）双端队列

二、第一周做题记录

Array 实战题目

• 盛最多水的容器（腾讯、百度、字节跳动在近半年内面试常考）
• 移动零（华为、字节跳动在近半年内面试常考）
• 爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）

• 三数之和（国内、国际大厂历年面试高频老题）

  Linked List 实战题目

• 反转链表（字节跳动、亚马逊在半年内面试常考）

• 两两交换链表中的节点（阿里巴巴、字节跳动在半年内面试常考）
• 环形链表（阿里巴巴、字节跳动、腾讯在半年内面试常考）
• 环形链表 II
• K 个一组翻转链表（字节跳动、猿辅导在半年内面试常考）

（一）Array 实战题目

1、盛最多水的容器（腾讯、百度、字节跳动在近半年内面试常考）

链接地址：https://leetcode-cn.com/problems/container-with-most-water/

11. 盛最多水的容器

难度中等2011收藏分享切换为英文接收动态反馈
给你 n 个非负整数 a，a...，a``n每个数代表坐标中的一个点 (i, a) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1

示例 3：
输入：height = [4,3,2,1,4]
输出：16

示例 4：
输入：height = [1,2,1]
输出：2

（1）第一种：

1. 枚举 left bar ,right bar,(x - y ) * height O(n^2)
2. 
   

对传递进来的数组进行双重循环，不断的维护i和j坐标。

public int maxArea(int[] height) {
    int max = 0;
    for(int i = 0; i < height.length -1 ; i++){
        for(int j = i + 1 ; j < height.length; j++){
            int area = ( j - i) * Math.min(height[i],height[j]);
            max = Math.max(area,max);
        }
    }
    return max;
}

2、移动零（华为、字节跳动在近半年内面试常考）

3、爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）

4、三数之和（国内、国际大厂历年面试高频老题）

（二）Linked List 实战题目

三、参考链接

参考链接

• Java 的 PriorityQueue 文档
• Java 的 Stack 源码
• Java 的 Queue 源码
• Python 的 heapq
• 高性能的 container 库

预习题目

• 有效的括号（亚马逊、JPMorgan 在半年内面试常考）

• 最小栈（亚马逊在半年内面试常考）

  实战题目

• 柱状图中最大的矩形（亚马逊、微软、字节跳动在半年内面试中考过）

• 滑动窗口最大值（亚马逊在半年内面试常考）

  课后作业

• 用 add first 或 add last 这套新的 API 改写 Deque 的代码

• 分析 Queue 和 Priority Queue 的源码
• 设计循环双端队列（Facebook 在 1 年内面试中考过）
• 接雨水（亚马逊、字节跳动、高盛集团、Facebook 在半年内面试常考）

说明：改写代码和分析源码这两项作业，同学们需要在第 1 周的学习总结中完成。如果不熟悉 Java 语言，这两项作业可选做。