ubuntu22.04为k8s部署NFS

Posted on 2026-02-28

ubuntu22.04为k8s部署NFS

在本篇博客中，我将介绍如何在 Ubuntu 系统中部署 NFS 服务，并在 Kubernetes 节点之间共享存储。

1. 安装 NFS 服务

在 k8s-master 节点上，我们需要先安装 nfs-kernel-server。可以通过以下命令安装：

1 2	root@k8s-master:~# cd /opt root@k8s-master:/opt# sudo apt install -y nfs-kernel-server

安装过程中，系统会提示安装一些必要的依赖包，例如 keyutils、nfs-common、rpcbind 等。

安装完成后，使用以下命令检查 NFS 服务是否已启动：

1 2	root@k8s-master:/opt# sudo systemctl start nfs-kernel-server root@k8s-master:/opt# sudo systemctl enable nfs-kernel-server

2. 配置共享目录

这个根据实际配置，我这里在 k8s-master 上创建共享目录 k8s_store，并修改权限：

1 2	root@k8s-master:/opt# mkdir k8s_store root@k8s-master:/opt# chmod 777 k8s_store/

查看目录内容：

1	root@k8s-master:/opt# ll -a

然后编辑 /etc/exports 文件，添加共享目录的配置：

1	root@k8s-master:/opt# vim /etc/exports

在文件末尾添加共享目录位置，我设置了以下行：

1	/opt/k8s_store *(rw,sync,no_root_squash,no_subtree_check)

应用配置：

1	root@k8s-master:/opt# sudo exportfs -a

3. 启动 NFS 服务

启动并使 NFS 服务在系统启动时自动启动：

1 2	root@k8s-master:/opt# sudo systemctl start nfs-kernel-server root@k8s-master:/opt# sudo systemctl enable nfs-kernel-server

4. 在客户端安装 NFS

接下来，在 k8s-node1 节点上安装 NFS 客户端：

1	root@k8s-node1:~# sudo apt install -y nfs-common

安装过程中，系统会提示安装一些依赖包，例如 rpcbind 等。

安装完成后，创建挂载点并挂载 NFS 共享目录：

1 2	root@k8s-node1:~# sudo mkdir -p /opt/k8s_store root@k8s-node1:~# mount -t nfs 192.168.126.160:/opt/k8s_store /opt/k8s_store

完成

ubuntu22.04部署k8s1.23.6

Posted on 2026-02-23 Edited on 2026-02-28

ubuntu22.04部署k8s1.23.6

Kubernetes 集群部署学习笔记（一）：基础环境准备

记录时间：2026-02-19
系统环境：Ubuntu 22.04
本节内容：系统初始化与内核参数配置

一、切换 root 用户

sudo -i

后续操作大多涉及系统级修改，直接使用 root 用户进行。

二、关闭 Swap（必须）

Kubernetes 要求关闭 swap，否则 kubelet 无法正常启动。

1. 临时关闭

1	swapoff -a

2. 永久关闭

编辑 /etc/fstab：

1	vi /etc/fstab

原内容中 swap 行：

1	# /swapfile none swap sw 0 0

确保 swap 行被注释（前面加 #）。

查看确认：

1	cat /etc/fstab

三、加载内核模块

Kubernetes 网络依赖以下两个模块：

overlay
br_netfilter

创建配置文件：

cat <<EOF | tee /etc/modules-load.d/k8s.conf
overlay
br_netfilter
EOF

手动加载模块：

1 2	modprobe overlay modprobe br_netfilter

查看是否加载成功：

1 2	lsmod \| grep overlay lsmod \| grep br_netfilter

四、关闭防火墙（实验环境）

1	ufw disable

注意：生产环境不建议直接关闭防火墙，应配置规则放行端口。

五、设置时区与时间同步

统一所有节点时间非常重要，否则证书和集群通信可能出问题。

设置时区：

1	timedatectl set-timezone Asia/Shanghai

重启时间同步服务：

1	systemctl restart systemd-timesyncd.service

查看当前时间：

date

六、修改主机名

为不同节点设置独立主机名：

1 2	hostnamectl set-hostname k8s-node2 exec bash

七、配置 /etc/hosts

为了方便节点之间解析主机名，编辑：

1	vim /etc/hosts

内容示例：

127.0.0.1   localhost
127.0.1.1   k8s-node2

192.168.126.160   k8s-master
192.168.126.161   k8s-node1
192.168.126.162   k8s-node2

八、配置内核转发参数

Kubernetes 网络需要开启 IP 转发。

创建配置文件：

1
2
3

cat <<EOF | sudo tee /etc/sysctl.d/k8s.conf
net.ipv4.ip_forward = 1
EOF

如果有需要，可以同时加入

1 2	net.bridge.bridge-nf-call-iptables = 1 net.bridge.bridge-nf-call-ip6tables = 1

使配置生效：

1	sysctl --system

验证：

1	sysctl net.ipv4.ip_forward

输出应为：

1	net.ipv4.ip_forward = 1

九、本阶段小结

本节完成内容：

关闭 swap
加载关键内核模块
关闭防火墙（实验环境）
统一时区
配置主机名
设置 hosts 互相解析
开启 IP 转发

这些属于 Kubernetes 部署前的基础系统准备工作。

下一步将进入容器运行时安装与 Kubernetes 组件安装。

Kubernetes 1.23.6 部署记录（二）——组件安装与镜像问题排查

系统环境：

Ubuntu 22.04.5 LTS
内核版本：6.8.0-94-generic
主机名：k8s-master
Kubernetes 版本：1.23.6

一、配置 Docker

kubelet的 cgroup driver 默认为 systemd，为了保证 Kubernetes 正常运行，需要将 Docker 的 cgroup driver 设置为 systemd。

创建或修改 /etc/docker/daemon.json：

cat <<EOF | sudo tee /etc/docker/daemon.json
{
  "exec-opts": ["native.cgroupdriver=systemd"],
  "log-driver": "json-file",
  "log-opts": {
    "max-size": "10m"
  },
  "storage-driver": "overlay2"
}
EOF

重启并设置开机自启：

1 2	systemctl restart docker systemctl enable docker

二、配置 Kubernetes 阿里云软件源

添加 apt key（虽然提示 deprecated，但当前仍可使用）：

1	curl https://mirrors.aliyun.com/kubernetes/apt/doc/apt-key.gpg \| apt-key add -

添加软件源：

1	echo "deb https://mirrors.aliyun.com/kubernetes/apt kubernetes-xenial main" >> /etc/apt/sources.list

更新索引：

1	apt-get update

会看到 legacy trusted.gpg 的警告，目前不影响安装。

三、安装指定版本 Kubernetes 组件

必须指定版本号，否则会安装最新版本。

1	apt-get install -y kubelet=1.23.6-00 kubeadm=1.23.6-00 kubectl=1.23.6-00

安装过程中会自动安装：

cri-tools
kubernetes-cni
conntrack
ebtables
socat

安装完成后锁定版本，防止自动升级：

1	apt-mark hold kubelet kubeadm kubectl

四、提前拉取控制面镜像

使用阿里云镜像仓库拉取 Kubernetes 所需镜像：

1 2	kubeadm config images pull \ --image-repository registry.cn-hangzhou.aliyuncs.com/google_containers

输出显示：

kube-apiserver
kube-controller-manager
kube-scheduler
kube-proxy
pause
etcd
coredns

提示远程版本较新，但自动回退到 stable-1.23，是正常现象。

五、Docker 拉取镜像失败问题

测试拉取：

1	docker pull nginx

报错：

1	context deadline exceeded

说明当前环境无法直接访问 Docker Hub。

六、配置 Docker 镜像加速/代理

编辑 /etc/docker/daemon.json，增加 registry-mirrors 字段：

{
  "exec-opts": ["native.cgroupdriver=systemd"],
  "log-driver": "json-file",
  "log-opts": {
    "max-size": "10m"
  },
  "storage-driver": "overlay2",
  "registry-mirrors": [
    "https://dockerproxy.com",
    "https://docker.m.daocloud.io",
    "https://hub.rat.dev",
    "https://docker.xuanyuan.me",
    "https://docker.1ms.run"
  ]
}

重新加载并重启：

1 2	sudo systemctl daemon-reload sudo systemctl restart docker

验证配置是否生效：

1	docker info

确认：

Cgroup Driver: systemd
Storage Driver: overlay2
Registry Mirrors 已加载

再次执行：

1	docker pull nginx

仍然出现：

1	Get "https://registry-1.docker.io/v2/": context deadline exceeded

即使配置了镜像加速器，仍可能出现 docker pull nginx 超时（如 context deadline exceeded）。这通常由以下原因导致：

加速器地址失效或网络不通
节点网络出口受限（如防火墙、代理限制）
DNS 解析问题

解决方法：

尝试更换其他可用的加速器地址
或者采用离线镜像分发方案（见部署记录（四））

如果加速器无效可以给docker配置代理：

① 创建 systemd 目录（如已存在可忽略）

1	sudo mkdir -p /etc/systemd/system/docker.service.d

② 创建 Docker 代理配置文件

1	sudo nano /etc/systemd/system/docker.service.d/proxy.conf

写入以下内容（代理服务器地址需要允许局域访问）：

[Service]
Environment="HTTP_PROXY=http://192.168.1.100:7890"
Environment="HTTPS_PROXY=http://192.168.1.100:7890"
Environment="NO_PROXY=localhost,127.0.0.1,192.168.0.0/16,10.0.0.0/8,10.244.0.0/16,10.96.0.0/12,.cluster.local"

其中 NO_PROXY 配置非常关键，用于避免集群内部流量被错误地转发到代理。

如果未正确配置 NO_PROXY，可能导致以下问题：

Pod 内部访问异常
Kubernetes API Server 访问异常
Cilium 等 CNI 组件通信异常

上述问题通常表现为网络不可达或组件反复重启，严重时会导致集群不可用。

③ 重载 systemd 并重启 Docker 服务

1 2	sudo systemctl daemon-reload sudo systemctl restart docker

④ 验证 Docker 是否已加载代理环境变量

1	systemctl show --property=Environment docker

期望看到类似输出：

1 2	HTTP_PROXY=http://192.168.1.100:7890 HTTPS_PROXY=http://192.168.1.100:7890

⑤ 拉取镜像进行验证

1	docker pull cr.fluentbit.io/fluent/fluent-bit:4.2.2

镜像能够成功拉取，说明 Docker 代理配置生效。

Kubernetes 1.23.6 部署记录（三）——初始化集群与安装 Cilium

一、初始化 Kubernetes 集群（跳过 kube-proxy）

由于后续使用 Cilium 并启用 kubeProxyReplacement，因此在初始化阶段跳过 kube-proxy 的安装。

执行：

kubeadm init \
  --apiserver-advertise-address=192.168.126.160 \
  --pod-network-cidr=10.244.0.0/16 \
  --skip-phases=addon/kube-proxy \
  --image-repository registry.cn-hangzhou.aliyuncs.com/google_containers

关键说明：

--apiserver-advertise-address：指定 apiserver 对外通信地址
--pod-network-cidr：指定 Pod 网段
--skip-phases=addon/kube-proxy：跳过 kube-proxy
--image-repository：使用阿里云镜像仓库

初始化成功后会提示：

1	Your Kubernetes control-plane has initialized successfully!

二、配置 kubectl 访问权限

根据提示执行：

1
2
3

mkdir -p $HOME/.kube
sudo cp -i /etc/kubernetes/admin.conf $HOME/.kube/config
sudo chown $(id -u):$(id -g) $HOME/.kube/config

验证节点状态：

1	kubectl get nodes

输出：

1	k8s-master NotReady control-plane,master v1.23.6

此时 NotReady 是正常现象，因为尚未安装 CNI 网络插件。

查看系统 Pod：

1	kubectl get pods -n kube-system

可以看到：

apiserver、controller-manager、scheduler、etcd 均 Running
coredns 为 Pending

原因：尚未安装网络插件。

三、安装 Helm

使用官方脚本安装 Helm：

1	curl https://raw.githubusercontent.com/helm/helm/main/scripts/get-helm-3 \| bash

验证：

1	helm version

四、使用 Helm 安装 Cilium

添加仓库：

1 2	helm repo add cilium https://helm.cilium.io/ helm repo update

安装 Cilium（版本 1.12.6）：

helm install cilium cilium/cilium --version 1.12.6 \
  --namespace kube-system \
  --set k8sServiceHost=192.168.126.160 \
  --set k8sServicePort=6443 \
  --set kubeProxyReplacement=strict \
  --set ipam.mode=kubernetes

参数说明：

k8sServiceHost：API Server 地址
k8sServicePort：API Server 端口
kubeProxyReplacement=strict：完全替代 kube-proxy
ipam.mode=kubernetes：使用 Kubernetes IPAM

安装成功后提示：

1	STATUS: deployed

五、验证集群状态

查看所有 Pod：

1	kubectl get po -A

结果：

cilium Pod Running
coredns 由 Pending 变为 Running
control-plane 组件正常

当前有一个 Pod 未就绪：

1	cilium-operator-xxxx 0/1 Pending

原因分析：

本实验环境为一主二从集群，目前仅有一个主节点。
Cilium Operator 默认存在 Pod 反亲和性规则，不允许调度到同一节点。
因此在只有一个节点时，会有一个副本 Pending。

当工作节点加入后，该 Pod 会自动调度并恢复正常。

六、加入工作节点

在从节点上执行初始化阶段输出的 join 命令，注意：token 默认有效期为 24 小时，如果之后需要添加新节点，请重新生成 token（kubeadm token create --print-join-command）。：

1 2	kubeadm join 192.168.126.160:6443 --token 5bhnb8.b0f6uopwwqb0t2xg \ --discovery-token-ca-cert-hash sha256:287c9c4ab79974eebecc5ddd1c36c033ac52c7c718cf3ab1f36365bb25db673c

加入成功后，在主节点查看：

1	kubectl get nodes

待节点 Ready 后，再查看：

1	kubectl get pods -n kube-system

此前 Pending 的 cilium-operator 将恢复为 Running。

当前阶段状态

control-plane 初始化完成
kube-proxy 已跳过
Cilium 已部署
CoreDNS 正常运行
等待工作节点加入完成集群规模扩展

Kubernetes 1.23.6 部署记录（四）——Cilium 镜像离线分发处理

一、问题背景

在安装 Cilium 后，发现从节点拉取 quay.io/cilium/cilium 镜像速度极慢，导致：

Pod 长时间处于 Init 状态
Cilium 启动时间过久
集群整体 Ready 时间被拖慢

因此采用离线镜像分发方式处理。

二、主节点导出 Cilium 镜像

在主节点确认镜像存在后，将镜像导出为 tar 包：

1	docker save quay.io/cilium/cilium:v1.12.6@sha256:454134506b0448c756398d3e8df68d474acde2a622ab58d0c7e8b272b5867d0d -o cilium.tar

查看文件：

ls

三、通过 scp 传输到从节点

首次执行：

1	scp *.tar root@192.168.126.161:/root/

报错：

1	ssh: connect to host 192.168.126.161 port 22: Connection refused

原因：从节点未安装或未启动 SSH 服务。

四、安装并启动 SSH 服务

在节点上执行：

1 2	sudo apt update sudo apt install -y openssh-server

启动并设置开机自启：

1 2	sudo systemctl start ssh sudo systemctl enable ssh

五、测试 SSH 连接

测试 root 登录：

1	ssh root@192.168.126.161

出现：

1	Permission denied (publickey,password)

说明 root 登录被禁用（默认安全策略）。

改用普通用户：

1	ssh user@192.168.126.161 "echo 'SSH connection successful'"

成功输出：

1	SSH connection successful

六、分发镜像文件

传输到两个从节点：

1 2	scp .tar user@192.168.126.161:~ scp .tar user@192.168.126.162:~

传输完成后，在对应从节点用户目录可以看到：

1	cilium.tar

七、从节点加载镜像

在每个从节点执行：

1	docker load -i cilium.tar

验证：

1	docker images \| grep cilium

确认镜像已成功导入。

八、效果

加载完成后：

Cilium Pod 不再从公网拉取镜像
Init 时间明显缩短
网络组件更快进入 Running 状态
集群整体 Ready 时间提升

小结

当网络环境不稳定或镜像仓库访问缓慢时，可以采用：

主节点提前拉取镜像
使用 docker save 导出
使用 scp 分发
从节点 docker load 导入

这种方式适用于：

内网环境
无公网环境
大规模节点初始化场景
镜像拉取频繁超时场景

Kubernetes 集群部署验证与优雅关闭实践

一、集群功能验证

集群部署完成后，使用 nginx 进行功能验证。

创建 Deployment：

1	kubectl create deployment nginx --image=nginx

暴露为 NodePort 服务：

1	kubectl expose deployment nginx --port=80 --type=NodePort

查看资源状态：

1	kubectl get pod,svc

初始状态：

Pod 处于 ContainerCreating
Service 分配 NodePort 端口（例如 30795）

查看调度情况：

1	kubectl get pods -o wide

可以看到：

Pod 被调度到某个工作节点（如 k8s-node2）
分配到 Pod 网段 IP（如 10.244.x.x）
状态 Running

说明：

Cilium 网络正常
Pod 调度正常
Service 正常创建

二、优雅关闭集群脚本设计

目标：

依次排空节点
停止 kubelet 与 Docker
最终安全关机

脚本依赖条件：

已配置 SSH 免密登录
已配置 sudo 免密码

脚本内容如下：

#!/bin/bash
# 优雅关闭 Kubernetes 集群脚本（使用 SSH 密钥认证）

SSH_USER="user"
MASTER_NODE="k8s-master"
WORKER_NODES=("k8s-node1" "k8s-node2")
ALL_NODES=("k8s-master" "k8s-node1" "k8s-node2")
SSH_OPTS="-o ConnectTimeout=10 -o ServerAliveInterval=5 -o StrictHostKeyChecking=no"

check_ssh() {
    local node=$1
    ssh -o BatchMode=yes -o ConnectTimeout=5 $SSH_USER@$node "exit" 2>/dev/null
    if [ $? -ne 0 ]; then
        echo "错误：无法免密登录到 $node"
        exit 1
    fi
}

echo "开始优雅关闭集群"

for node in "${ALL_NODES[@]}"; do
    check_ssh "$node"
done

for node in "${WORKER_NODES[@]}"; do
    kubectl drain "$node" --ignore-daemonsets --delete-emptydir-data
done

kubectl drain "$MASTER_NODE" --ignore-daemonsets --delete-emptydir-data

SERVICES="kubelet docker.socket docker"

for node in "${ALL_NODES[@]}"; do
    ssh $SSH_OPTS $SSH_USER@$node "sudo systemctl stop $SERVICES"
done

echo "集群服务已停止"

三、SSH 免密配置

主节点生成密钥：

1	ssh-keygen -t rsa -b 4096 -N "" -f ~/.ssh/id_rsa

分发公钥：

1
2
3

ssh-copy-id user@k8s-master
ssh-copy-id user@k8s-node1
ssh-copy-id user@k8s-node2

四、配置 sudo 免密码

在每个节点执行：

1 2	echo "user ALL=(ALL) NOPASSWD: ALL" \| sudo tee /etc/sudoers.d/user-nopasswd sudo chmod 440 /etc/sudoers.d/user-nopasswd

五、Terminating 状态处理

如果存在 Pod 卡在 Terminating 状态，kubectl drain 可能会阻塞。

例如：

1	cilium-operator-xxxxx Terminating

可以强制删除：

1	kubectl -n kube-system delete pod <pod-name> --force --grace-period=0

注意：

这是立即删除
可能存在残留资源
仅在必要时使用

六、脚本执行效果

执行：

1	./close-claster.sh

执行过程：

校验 SSH 连接
依次 cordon + drain 工作节点
排空主节点
停止 kubelet 和 docker
输出关闭完成提示

验证服务状态：

1 2	systemctl status kubelet systemctl status docker

状态应为：

1	Active: inactive (dead)

说明：

kubelet 已停止
docker 已停止
容器已清理
卷已卸载

七、最终关机

确认所有节点服务停止后：

1	shutdown -h now

至此集群已安全关闭。

本阶段总结

本阶段完成：

集群功能验证
NodePort 服务验证
优雅关闭流程设计
SSH 免密与 sudo 免密配置
Terminating Pod 异常处理

整体流程验证无误，可作为日常实验环境启停的标准操作流程。

ubuntu22.04配置静态ip

Posted on 2026-02-10 Edited on 2026-02-19

Ubuntu 22.04 配置静态 IP

本文记录一次在 Ubuntu 22.04 系统中配置静态 IP 的过程。作为初学者，整理操作步骤与关键点，便于后续复现和排查问题。

一、环境说明

系统版本：Ubuntu 22.04
主机名：node0
网卡名称：ens33
配置目标：将 DHCP 修改为静态 IP

二、修改 Netplan 配置文件

Ubuntu 18.04 及以后版本默认使用 Netplan 管理网络配置，相关文件位于：

1	/etc/netplan/

编辑之前，可选使用cp指令备份原文件。

1. 编辑配置文件

1	root@node0:/etc/netplan# vim 01-network-manager-all.yaml

配置内容如下：

network:
    ethernets:
        ens33:                    # 网卡名称
            dhcp4: false
            addresses:
              - 192.168.126.160/24   # 静态IP

            routes:
              - to: default
                via: 192.168.126.2   # 网关

            nameservers:
              addresses: [8.8.8.8,114.114.114.114,192.168.126.2]
    version: 2
    renderer: NetworkManager

2. 参数说明

dhcp4: false：关闭 IPv4 DHCP
addresses：设置静态 IP 地址及子网掩码
routes：配置默认网关
nameservers：设置 DNS 服务器
renderer：指定网络管理方式

需要注意，YAML 文件对缩进要求严格，只能使用空格，不能使用 Tab。

三、生成并应用配置

1 2	root@node0:/etc/netplan# netplan generate root@node0:/etc/netplan# netplan apply

若无报错信息，说明配置语法正确。

netplan generate：根据 /etc/netplan/ 目录下的 YAML 配置文件生成后端（NetworkManager）可用的实际配置文件，相当于“编译”配置但尚未应用。
netplan apply：将生成的配置立即应用到系统中，包括重启网络服务、重新配置网络接口，使静态 IP 等设置生效。

四、启动并检查网卡状态

1. 启动网卡

1	root@node0:/etc/netplan# ip link set ens33 up

2. 查看网卡状态

1	root@node0:/etc/netplan# ip link show ens33

输出信息中若包含 UP，表示网卡已正常启用。

五、验证 IP 配置结果

1	root@node0:/etc/netplan# ip a

可以看到如下内容：

1	inet 192.168.126.160/24 brd 192.168.126.255 scope global noprefixroute ens33

说明静态 IP 已成功生效。

六、测试网络连通性

1	root@node0:/etc/netplan# ping baidu.com

结果显示：

1	3 packets transmitted, 3 received, 0% packet loss

说明 DNS 解析正常，网关配置正确，网络可以正常访问外部地址。

七、问题记录

YAML 缩进错误会导致 netplan apply 执行失败。
配置前应先通过 ip a 确认实际网卡名称。

八、小结

通过本次实践，了解了 Ubuntu 22.04 使用 Netplan 进行网络管理的基本方法。静态 IP 配置主要涉及 IP 地址、网关和 DNS 三部分内容。实际操作中需特别注意配置文件格式与缩进问题。

本文作为个人操作记录，供后续参考。

135.分发糖果

Posted on 2025-11-14 Edited on 2025-11-16 In leetcode , 面试经典150题

贪心

题目要求相邻的孩子较多一方那个获得更多糖果，也就是说糖果发放取决于数组走势（上升or下降），因此可以将数组分为若干相似得山峰并分组求解，每座山中从两端山脚开始糖果依次递增，最多糖果为山峰。

双向遍历，分别满足山峰大于左边和山峰大于右边即可。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                ans[i] = ans[i - 1] + 1;
            }
        }
        for(int i = n - 2; i >= 0; --i) {
            if(ratings[i] > ratings[i + 1]) {
                ans[i] = Math.max(ans[i], ans[i + 1] + 1);
            }
        }
        return Arrays.stream(ans).sum();
    }
}

也可以考虑一次遍历，考虑可能出现共享波谷，如1 4 5 2 0 1 4 5 2 中的0，他应该分应1颗糖果，如果直接统计1 4 5 2 0和 0 1 4 5 2两座山会导致0分配1颗糖果重复计算，所以事先为每人先分1颗糖果，这样在分组求解时山脚分0颗即可，避免了重复计算。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length, ans = n;  // 每人先分一颗
        for (int i = 0; i < n; ++i) {
            int start = i > 0 && ratings[i - 1] < ratings[i] ? i - 1 : i;
            while (i + 1 < n && ratings[i] < ratings[i + 1]) { // 严格递增段
                i++;
            }
            int top = i;
            while (i + 1 < n && ratings[i] > ratings[i + 1]) { // 严格递减段
                i++;
            }
            int increase = top - start;  // 严格递增得步数
            int decrease = i - top;  // 严格递减得步数
            int num1 = increase * (0 + increase - 1) / 2;
            int num2 = decrease * (decrease - 1 + 0) / 2;
            ans += num1 + num2 + Math.max(increase, decrease);
        }
        return ans;
    }
}

134.加油站

Posted on 2025-11-11 In leetcode , 面试经典150题

贪心

首先，总油量 ≥ 总消耗量是存在解得充分必要条件。

证明：

设 net[i] = gas[i] - cost[i]（每个加油站的净收益）

条件1：必要性

如果总油量 < 总消耗量，即 Σnet[i] < 0

那么无论如何选择起点，总油量都不够绕一圈

必要条件成立

**条件2：充分性

假设 Σnet[i] ≥ 0，但不存在任何起点可以完成环路。

这意味着：对于每一个可能的起点 k，在绕行过程中都会在某个点出现油量不足。

假设从起点 k出发，在到达点 m时第一次出现油量不足，那么：

从 k到 m的净收益总和 < 0
由于总净收益 ≥ 0，那么从 m回到 k的净收益总和必须 > 0
矛盾！因为如果从 m回到 k的净收益 > 0，那么从 m出发应该能够完成环路

充分条件成立

因此，只需要

1 统计总油量 ≥ 总消耗量
2 满足 1 的时候找到起点，实现方式为当我们发现某段路程总消耗量 ≥总油量为负时候把下一个当作起点即可

时间复杂度：$O(n)$

空间复杂度：$O(1)$

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length, sumGas = 0, curGas = 0, start = 0;
        for (int i = 0; i < n; ++i) {
            sumGas += gas[i] - cost[i];
            curGas += gas[i] - cost[i];
            if (curGas < 0) {
                curGas = 0;
                start = i + 1;
            }
        }
        return sumGas >= 0 ? start : -1;
    }
}

238.除自身以外数组的乘积

Posted on 2025-11-10 In leetcode , 面试经典150题

前缀和

时间复杂度：$O(n)$

空间复杂度：$O(1)$，返回值不计入返回值

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[n - 1] = 1;
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = ans[i + 1] * nums[i + 1];
        };
        int pre = 1;
        for (int i = 0; i < n; ++i) {
            ans[i] *= pre;
            pre *= nums[i];
        }
        return ans;
    }
}

380.O(1)时间插入、删除和获取随机元素

Posted on 2025-11-09 In leetcode , 面试经典150题

哈希表

题目要求插入、删除、随机删除复杂度均为$O(1)$，其中需要判断元素是否在集合中，所以查询特定值的复杂度也需要达到$O(1)$，常见数据结构中：

数据结构	插入复杂度	删除复杂度	查询特定值	随机查找
数组	末尾$O(1)$，中间与首部$O(n)$	末尾$O(1)$，中间与首部$O(n)$	$O(n)$	支持
列表	$O(1)$	在已经找到节点的情况下为$O(1)$	$O(n)$	不支持
哈希表	$O(1)$	$O(1)$	$O(1)$	不支持

没有任何一种可以直接满足要求，所以需要组合使用。

此处选取的思路为底层用数组存储数据，支持随机查找需求，插入直接向末尾插入以实现$O(1)$复杂度，删除时交换到数组末尾来达到$O(1)$需求，哈希表采用val-index映射负责维护查询特定值所需的$O(1)$复杂度。

实现中下面的代码给数组预分配了内存并维护指向第一个可用位置的tail指针，这部分可以使用ArrayList代替。

时间复杂度：所有函数均为$O(1)$

空间复杂度：$O(n)$，$n$ 为最大元素数量

class RandomizedSet {
    private Map<Integer, Integer> map = new HashMap<>();
    private int[] cnt = new int[200001];
    private int tail = 0;
    private Random random = new Random();
    public RandomizedSet() {

    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, tail);
        cnt[tail++] = val;
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int idx = map.get(val);
        if (idx != tail - 1) {
            swap(cnt, idx, tail - 1);  // 交换到数组末尾
            map.put(cnt[idx], idx);  // 末尾元素索引更新
        }
        map.remove(val);
        tail--;
        return true;
    }
    
    public int getRandom() {
        return cnt[random.nextInt(tail)];
    }

    private void swap (int[] a, int l, int r) {
        int tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

274.H指数

Posted on 2025-11-09 In leetcode , 面试经典150题

计数排序+后缀和

时间复杂度$O(n)$

空间复杂度$O(n)$

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] cnt = new int[n + 1];
        for (int x : citations) {
            x = x > n ? n : x;  // 截断
            cnt[x]++;
        }
        int ans = 0, sufSum = 0;
        for (int i = n; i > 0; --i) {
            sufSum += cnt[i];
            ans = Math.max(ans, Math.min(i, sufSum));  // 引用书和论文量均不小于
        }
        return ans;
    }
}

45.跳跃游戏Ⅱ

Posted on 2025-11-08 Edited on 2025-11-09 In leetcode , 面试经典150题

贪心

时间复杂度$O(n)$

空间复杂度$O(1)$

class Solution {
    public int jump(int[] nums) {
        int ans = 0, n = nums.length, right = 0, newRight = 0;
        for (int i = 0; i < n; ++i) {
            if (right >= n - 1) {
                break;
            }
            newRight = Math.max(newRight, i + nums[i]);
            if (i == right) {
                right = newRight;
                ans++;
            }
        }
        return ans;
    }
}

55.跳跃游戏

Posted on 2025-11-08 Edited on 2025-11-09 In leetcode , 面试经典150题

贪心

时间复杂度$O(n)$

空间复杂度$O(1)$

class Solution {
    public boolean canJump(int[] nums) {
        int right = 0, n = nums.length;
        for (int i = 0; i < n && i <= right; ++i) {
            right = Math.max(right, i + nums[i]);
            if (right >= n - 1) {
                break;
            }
        }
        return right >= n - 1;
    }
}