Sooner or later, every Nginx configuration grows beyond a single catch-all rule. You want PHP files to reach PHP-FPM, static assets to be served directly with long cache headers, one endpoint to be proxied to an application server, and an admin path to be protected with basic auth. Each of these rules lives in its own location block.

The part that trips people up is not writing a location block, it is predicting which one Nginx will pick when a request could match more than one. Nginx does not scan top to bottom. It uses a specific priority order that mixes prefix length, match type, and regex ordering. This guide walks through the match types, the exact order Nginx follows, and the patterns you will use most often.

Location Block Syntax #

A location block lives inside a server block and defines how Nginx handles requests whose URI matches a given pattern:

location [modifier] pattern {
 # directives
}

The modifier is optional. When it is omitted, Nginx treats the pattern as a prefix. The pattern is a string (for prefix and exact matches) or a regular expression (when the modifier is ~ or ~*).

A minimal server block that uses two location blocks looks like this:

server {
 listen 80;
 server_name example.com;
 root /var/www/example.com;

 location / {
 try_files $uri $uri/ =404;
 }

 location /api/ {
 proxy_pass http://127.0.0.1:3000;
 }
}

Requests for /about.html fall into the first block and are served as static files. Requests for /api/users fall into the second block and are proxied to the application.

The Five Match Types #

Nginx supports five kinds of location matches. Each one uses a different modifier, and each one has its own role in the priority order covered in the next section.

• location /path/ - Prefix match. Matches any URI that begins with the given string. This is the default when no modifier is used.
• location = /path - Exact match. Matches only when the request URI is exactly equal to the given string.
• location ^~ /path/ - Preferential prefix match. Same matching rules as a plain prefix match, but tells Nginx to stop searching for regex matches once this block is selected as the longest prefix.
• location ~ pattern - Case-sensitive regex match. Matches if the URI matches the regular expression.
• location ~* pattern - Case-insensitive regex match. Same as ~, but ignores letter case.

There is also a sixth form, location @name, for named locations. Named locations are not used during the normal match process; they are jumped to from directives such as try_files and error_page. We cover them later in this guide.

How Nginx Picks a Location #

When a request comes in, Nginx does not walk through location blocks top to bottom. It picks the block that wins according to a fixed priority order.

The order Nginx follows is:

1. Look for an exact match (=). If one matches, stop and use it.
2. Look at all prefix matches (plain and ^~) and remember the longest one that matches.
3. If the longest prefix match was defined with ^~, stop and use it.
4. Otherwise, go through regex matches (~ and ~*) in the order they appear in the configuration. The first one that matches wins.
5. If no regex matches, fall back to the longest prefix match remembered in step 2.

The consequences of this order are worth pausing on. Regex blocks are checked in source order, but prefix blocks are not; the longest match wins regardless of position in the file. The ^~ modifier changes the outcome by skipping the regex pass entirely when it is the longest prefix match, even if a regex block would also have matched.

A Worked Example #

The easiest way to understand the priority order is to trace a few requests through a real configuration:

server {
 listen 80;
 server_name example.com;
 root /var/www/example.com;

 location = / {
 return 200 "home\n";
 }

 location / {
 try_files $uri $uri/ =404;
 }

 location /images/ {
 expires 30d;
 }

 location ^~ /downloads/ {
 autoindex on;
 }

 location ~* \.(png|jpg|jpeg|gif)$ {
 expires 7d;
 access_log off;
 }

 location ~ \.php$ {
 fastcgi_pass unix:/run/php/php-fpm.sock;
 include fastcgi_params;
 }
}

Now trace what happens for a few requests:

• GET /: The = block matches exactly and wins immediately. Nginx returns the text home.
• GET /about.html: No exact match, no ^~ match, and no regex match. The longest prefix match is /, so the try_files block serves the static file.
• GET /images/logo.png: The longest prefix match is /images/, which is a plain prefix (no ^~), so regex checking still happens. The first regex to match is the image extension block (~*), so that block wins and the file is served with a 7-day expiry.
• GET /downloads/setup.exe: The longest prefix match is /downloads/, defined with ^~. Because of the ^~, regex checking is skipped and the directory listing block wins.
• GET /info.php: The longest prefix match is /. Regex checking runs, and the \.php$ block matches, so the request is passed to PHP-FPM.

Notice that the block order in the file did not change the outcome for prefix matches. It only changed the outcome for regex matches, where the first match wins.

Named Locations #

A named location starts with @ and does not take part in the matching logic. You can only enter a named location by being redirected there from another directive:

server {
 listen 80;
 server_name example.com;
 root /var/www/example.com;

 location / {
 try_files $uri $uri/ @fallback;
 }

 location @fallback {
 proxy_pass http://127.0.0.1:3000;
 }
}

In this configuration, Nginx first tries to serve the request as a static file. If the file is not found, try_files jumps to @fallback, which proxies the request to an application server on port 3000. This is a common pattern for single-page apps and for frameworks that handle their own routing.

Named locations are also useful with the error_page directive, where you can route errors into a named block that returns a custom response.

Common Patterns #

Most Nginx configurations end up using a handful of recurring location patterns. The snippets below show the shapes you will reach for most often.

Serve Static Files with a Fallback #

location / {
 try_files $uri $uri/ /index.html;
}

Nginx tries the requested URI as a file, then as a directory, and falls back to /index.html. This works well for single-page apps where the router lives in the browser.

Cache Long-Lived Assets #

location ~* \.(?:css|js|woff2?|png|jpg|jpeg|gif|svg|ico)$ {
 expires 30d;
 add_header Cache-Control "public, immutable";
 access_log off;
}

Assets whose content is fingerprinted by the build pipeline can be cached aggressively. The access_log off directive keeps the access log focused on real page requests; see the Nginx log files guide for where those logs live and how to tune them.

Pass PHP Requests to PHP-FPM #

location ~ \.php$ {
 include snippets/fastcgi-php.conf;
 fastcgi_pass unix:/run/php/php-fpm.sock;
}

The regex matches any URI that ends with .php. The fastcgi-php.conf snippet shipped with most distributions sets the correct SCRIPT_FILENAME and related parameters.

Proxy a Path to an Application #

location /api/ {
 proxy_pass http://127.0.0.1:3000;
 proxy_set_header Host $host;
 proxy_set_header X-Real-IP $remote_addr;
 proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
 proxy_set_header X-Forwarded-Proto $scheme;
}

For a deeper walkthrough of the proxy headers and common pitfalls, see the Nginx reverse proxy guide .

Protect an Admin Path #

location ^~ /admin/ {
 auth_basic "Restricted";
 auth_basic_user_file /etc/nginx/.htpasswd;
}

The ^~ modifier makes sure this block wins over any regex block (for example, a generic static-asset rule), so the auth challenge is not accidentally bypassed by a more specific pattern. Basic auth sends credentials in clear text, so serve the site over HTTPS; see how to redirect HTTP to HTTPS in Nginx .

Test the Configuration #

After changing location blocks, always test the Nginx configuration before reloading the service:

sudo nginx -t

If the syntax check passes, reload Nginx so the change takes effect without dropping active connections:

sudo systemctl reload nginx

If the test fails, Nginx prints the file name and line number that caused the error. Fix that issue first, then run sudo nginx -t again.

Quick Reference #

Common Mistakes #

A few patterns cause most of the confusion around location blocks.

Assuming top-to-bottom evaluation. Moving a prefix block higher in the file does not make it more likely to match. Prefix matches are chosen by length, not by position.

Forgetting that ^~ skips regex. If a request matches both a ^~ prefix and a regex block, the regex block is not evaluated. This is a feature, not a bug, but it is easy to forget when debugging why a regex rule is being ignored.

Trailing slashes. location /images/ and location /images behave differently. The first only matches URIs that start with /images/, while the second also matches /imagesfoo. Stick to trailing slashes for directory-like prefixes.

Using proxy_pass with a trailing slash on the upstream. Writing proxy_pass http://backend/; rewrites the path in a different way than proxy_pass http://backend;. The Nginx proxy_pass documentation explains the URI replacement rules in detail.

Regex order. When two regex blocks can match the same URI, the one that appears first in the config wins. If requests are landing in the wrong regex block, check the order.

Conclusion #

Most Nginx misconfigurations come from assumptions about the order of evaluation, not from the directives themselves. Once you know that exact matches win first, that ^~ can short-circuit the regex pass, and that regex blocks are tried in source order, the behavior of a complex server block becomes predictable.

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

• actuali 是完成第 i 个任务 需要耗费 的实际能量。
• minimumi 是开始第 i 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

提示：

• 1 <= tasks.length <= 105
• 1 <= actuali <= minimumi <= 104

按照什么规则排序？

本文把 $\textit{actual}$ 简称为 $a$，把 $\textit{minimum}$ 简称为 $m$。

如果 $\textit{tasks}$ 的某个排列 $T$ 是最优的（完成所有任务所需的初始能量最少），那么 $T$ 中的相邻任务满足什么性质？

设 $T$ 中的一对相邻任务为 $t_1 = (a_1,m_1)$ 和 $t_2 = (a_2,m_2)$。设初始能量为 $E_0$，完成这两个任务之前的能量为 $E$。由于从一开始到完成这两个任务之前，所消耗的能量之和是固定的 $S$，所以有 $E = E_0-S$。根据该式，$E$ 越小，初始能量 $E_0$ 也越小。

先完成哪个任务更好？

• 如果先完成 $t_1$ 再完成 $t_2$，那么完成 $t_1$ 之前，必须满足 $E\ge m_1$；完成 $t_2$ 之前，必须满足 $E-a_1\ge m_2$。联立得 $E\ge \max(m_1,m_2+a_1)$。
• 如果先完成 $t_2$ 再完成 $t_1$，那么完成 $t_2$ 之前，必须满足 $E\ge m_2$；完成 $t_1$ 之前，必须满足 $E-a_2\ge m_1$。联立得 $E\ge \max(m_2,m_1+a_2)$。

如果先完成 $t_1$ 再完成 $t_2$ 更优（或者相同），则有

$$
\max(m_1,m_2+a_1)\le \max(m_2,m_1+a_2)
$$

两边同时减去 $a_1+a_2$，得

$$
\max(m_1-a_1-a_2,m_2-a_2)\le \max(m_2-a_1-a_2,m_1-a_1)
$$

为方便阅读，令 $X=m_1-a_1$，$Y = m_2-a_2$，上式化简为

$$
\max(X-a_2,Y)\le \max(Y-a_1,X)
$$

• 如果 $X<Y$，那么上式左侧等于 $Y$，右侧严格小于 $Y$（题目保证 $a_1 > 0$），此时 $\max(X-a_2,Y) > \max(Y-a_1,X)$。
• 如果 $X\ge Y$，那么上式左侧两个值都 $\le X$，右侧等于 $X$，此时 $\max(X-a_2,Y) \le \max(Y-a_1,X)$。

所以当且仅当 $X\ge Y$ 成立时，$\max(X-a_2,Y)\le \max(Y-a_1,X)$ 成立。

所以当且仅当 $m_1-a_1 \ge m_2-a_2$ 成立时，先完成 $t_1$ 再完成 $t_2$ 更优（或者相同）。

这意味着，对于 $\textit{tasks}$ 中的相邻任务，设左边的任务为 $(a_1,m_1)$，右边的任务为 $(a_2,m_2)$，如果 $m_1-a_1 < m_2-a_2$，那么交换这两个任务可以让初始能量变得更小（或者不变）。于是通过交换 $\textit{tasks}$ 的相邻任务（类似冒泡排序的过程），把 $\textit{tasks}$ 按照 $m_i-a_i$ 从大到小排序，可以得到 $\textit{tasks}$ 的最优排列。

计算初始能量（正序）

设初始能量为 $E_0$，设执行 $\textit{tasks}[i] = (a_i,m_i)$ 之前，累计耗费的能量为 $S$，那么当前能量为 $E_0 - S$，必须满足

$$
E_0 - S \ge m_i
$$

即

$$
E_0 \ge S + m_i
$$

由此可以得到 $n$ 个关于 $E_0$ 的下界，所有下界取最大值，即为答案。

###py

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda t: t[0] - t[1])  # 按照 minimum - actual 从大到小排序

        ans = 0
        s = 0  # 累计耗费的能量
        for actual, minimum in tasks:
            # 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            # 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = max(ans, s + minimum)
            s += actual
        return ans

###java

class Solution {
    public int minimumEffort(int[][] tasks) {
        // 按照 minimum - actual 从大到小排序
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));

        int ans = 0;
        int s = 0; // 累计耗费的能量
        for (int[] t : tasks) {
            int actual = t[0];
            int minimum = t[1];
            // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = Math.max(ans, s + minimum);
            s += actual;
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        ranges::sort(tasks, {}, [](auto& t) { return t[0] - t[1]; }); // 按照 minimum - actual 从大到小排序

        int ans = 0;
        int s = 0; // 累计耗费的能量
        for (auto& t : tasks) {
            int actual = t[0], minimum = t[1];
            // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = max(ans, s + minimum);
            s += actual;
        }
        return ans;
    }
};

###c

int cmp(const void* p, const void* q) {
    int* a = *(int**)p;
    int* b = *(int**)q;
    return (b[1] - b[0]) - (a[1] - a[0]); // 按照 minimum - actual 从大到小排序
}

int minimumEffort(int** tasks, int tasksSize, int* tasksColSize) {
    qsort(tasks, tasksSize, sizeof(int*), cmp);

    int ans = 0;
    int s = 0; // 累计耗费的能量
    for (int i = 0; i < tasksSize; i++) {
        int actual = tasks[i][0];
        int minimum = tasks[i][1];
        // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
        // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
        ans = MAX(ans, s + minimum);
        s += actual;
    }
    return ans;
}

###go

func minimumEffort(tasks [][]int) (ans int) {
slices.SortFunc(tasks, func(a, b []int) int {
return (b[1] - b[0]) - (a[1] - a[0]) // 按照 minimum - actual 从大到小排序
})

s := 0 // 累计耗费的能量
for _, t := range tasks {
actual, minimum := t[0], t[1]
// 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
// 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
ans = max(ans, s+minimum)
s += actual
}
return
}

###js

var minimumEffort = function(tasks) {
    tasks.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0])); // 按照 minimum - actual 从大到小排序

    let ans = 0;
    let s = 0; // 累计耗费的能量
    for (const [actual, minimum] of tasks) {
        // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
        // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
        ans = Math.max(ans, s + minimum);
        s += actual;
    }
    return ans;
};

###rust

impl Solution {
    pub fn minimum_effort(mut tasks: Vec<Vec<i32>>) -> i32 {
        tasks.sort_unstable_by_key(|t| t[0] - t[1]); // 按照 minimum - actual 从大到小排序

        let mut ans = 0;
        let mut s = 0; // 累计耗费的能量
        for t in tasks {
            let actual = t[0];
            let minimum = t[1];
            // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = ans.max(s + minimum);
            s += actual;
        }
        ans
    }
}

计算初始能量（倒序）

也可以从右到左计算。

设完成任务 $t_i = (a_i,m_i)$ 之后的能量为 $E$，那么完成 $t_i$ 之前的能量为 $E+a_i$，但这个能量又必须 $\ge m_i$，所以完成 $t_i$ 之前的能量至少为

$$
\max(E+a_i, m_i)
$$

为了最小化初始能量，完成最后一个任务后的能量应当为 $0$，作为 $E$ 的初始值。

代码实现时，可以改成按照 $m_i-a_i$ 从小到大排序，这样可以正序遍历数组，更方便。

###py

class Solution:
    def minimumEffort(self, tasks: list[list[int]]) -> int:
        tasks.sort(key=lambda t: t[1] - t[0])  # 按照 minimum - actual 从小到大排序

        e = 0
        for actual, minimum in tasks:
            # 完成该任务之后的能量为 e，那么完成该任务之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = max(e + actual, minimum)
        return e

###java

class Solution {
    public int minimumEffort(int[][] tasks) {
        // 按照 minimum - actual 从小到大排序
        Arrays.sort(tasks, (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));

        int e = 0;
        for (int[] t : tasks) {
            int actual = t[0];
            int minimum = t[1];
            // 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = Math.max(e + actual, minimum);
        }
        return e;
    }
}

###cpp

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        ranges::sort(tasks, {}, [](auto& t) { return t[1] - t[0]; }); // 按照 minimum - actual 从小到大排序

        int e = 0;
        for (auto& t : tasks) {
            int actual = t[0], minimum = t[1];
            // 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = max(e + actual, minimum);
        }
        return e;
    }
};

###c

int cmp(const void* p, const void* q) {
    int* a = *(int**)p;
    int* b = *(int**)q;
    return (a[1] - a[0]) - (b[1] - b[0]); // 按照 minimum - actual 从小到大排序
}

int minimumEffort(int** tasks, int tasksSize, int* tasksColSize) {
    qsort(tasks, tasksSize, sizeof(int*), cmp);

    int e = 0;
    for (int i = 0; i < tasksSize; i++) {
        int actual = tasks[i][0];
        int minimum = tasks[i][1];
        // 完成 tasks[i] 之后的能量为 e，那么完成 tasks[i] 之前的能量为 e+actual，同时该能量必须至少为 minimum
        e = MAX(e + actual, minimum);
    }
    return e;
}

###go

func minimumEffort(tasks [][]int) (e int) {
slices.SortFunc(tasks, func(a, b []int) int {
return (a[1] - a[0]) - (b[1] - b[0]) // 按照 minimum - actual 从小到大排序
})

for _, t := range tasks {
actual, minimum := t[0], t[1]
// 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
e = max(e+actual, minimum)
}
return
}

###js

var minimumEffort = function(tasks) {
    tasks.sort((a, b) => (a[1] - a[0]) - (b[1] - b[0])); // 按照 minimum - actual 从小到大排序

    let e = 0;
    for (const [actual, minimum] of tasks) {
        // 完成该任务之后的能量为 e，那么完成该任务之前的能量为 e+actual，同时该能量必须至少为 minimum
        e = Math.max(e + actual, minimum);
    }
    return e;
};

###rust

impl Solution {
    pub fn minimum_effort(mut tasks: Vec<Vec<i32>>) -> i32 {
        tasks.sort_unstable_by_key(|t| t[1] - t[0]); // 按照 minimum - actual 从小到大排序

        let mut e = 0;
        for t in tasks {
            let actual = t[0];
            let minimum = t[1];
            // 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = minimum.max(e + actual);
        }
        e
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{tasks}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。不计入排序的栈开销。

专题训练

见下面贪心题单的「§1.7 交换论证法」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

【儿须成名酒须醉】Python3+排序+贪心+数学证明+模拟

提交结果

• 执行用时： 164 ms , 在所有 Python3 提交中击败了 94.62% 的用户
• 内存消耗： 42.6 MB , 在所有 Python3 提交中击败了 58.06% 的用户
• 通过测试用例： 42 / 42

解题思路

1. 考虑两个任务的能量组合任务1为$[a_1,m_1]$与任务2为$[a_2,m_2]$
2. 则先做任务1再做任务2的最小初始能量为$s_{12}=max(m_1,m_2+a_1)$，反之则是$s_{21}=max(m_2,m_1+a_2)$
3. 不失一般地设$m_1-a_1>=m_2-a_2$，则有$m_1+a_2>=m_2+a_1$

• 当$m_1<=m_2$时，显然有$s_{12}=m_2+a_1$，而$s_{21}=max(m_2,m_1+a_2)$，由上可得$m_2+a_1<=m_1+a_2$，因此有$s_{12}<=s_{21}$
• 当$m_1>m_2$时，显然有$s_{12}=max(m_1,m_2+a_1)$，而$s_{21}=m_1+a_2$，由上可得$m_2+a_1<=m_1+a_2$，因此有$s_{12}<=s_{21}$

4. 由此使用归纳法可知，贪心地将任务$[a,m]$当中$m-a$较大即$a-m$较小的排在前面进行即可

性能优化

• 无

复杂度分析

• 设任务个数为$n$，则有
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(1)$

代码

###python3

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[0] - x[1])
        ans = 0
        cur = 0
        for a, m in tasks:
            if cur < m:
                ans += m - cur
                cur = m
            cur -= a
        return ans

逆向思维

从结果状态反推：$初始能量=总消耗能量+剩余能量$ 在剩余能量为$0$时的初始能量最优

• 执行用时： 180 ms , 在所有 Python3 提交中击败了 80.65% 的用户
• 内存消耗： 42.5 MB , 在所有 Python3 提交中击败了 81.72% 的用户
• 通过测试用例： 42 / 42

代码

###python3

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0])
        ans = 0
        for a, m in tasks:
            ans = ans + a if ans + a > m else m
        return ans