Python 3, 38 34 33 bytes

lambda s:s==sorted(s,key=s.index)

This expects a list of digits or singleton strings as argument. Test it on Ideone.

Thanks to @xsot for golfing off 4 bytes!

Thanks to @immibis for golfing off 1 byte!

JavaScript (ES6), 27 bytes

s=>!/(.)(?!\1).*\1/.test(s)

Uses negative lookahead to look for two non-contiguous digits. If at least two such digits exist, then they can be chosen so that the first digit precedes a different digit.

Jelly, 5 bytes

ĠIFPỊ

Try it online!

How it works

ĠIFPỊ  Main link. Input: n (list of digits or integer)

Ġ      Group the indices of n by their corresponding values, in ascending order.
       For 8884443334, this yields [[7, 8, 9], [4, 5, 6, 10], [1, 2, 3]].
 I     Increments; compute the all differences of consecutive numbers.
       For 8884443334, this yields [[1, 1], [1, 1, 4], [1, 1]].
  F    Flatten the resulting 2D list of increments.
   P   Product; multiply all increments.
    Ị  Insignificant; check if the product's absolute value is 1 or smaller.

Pyth, 6 5 bytes

1 bytes thanks to FryAmTheEggman

SIxLQ

Inspired by the Python solution here.

Test suite

Explanation:

SIxLQ
  xLQ   Map each element in the input to its index in the input. Input is implicit.
SI      Check whether this list is sorted.

05AB1E, 4 bytes

Code:

Ô¹ÙQ

Explanation:

Ô     # Push connected uniquified input. E.g. 111223345565 would give 1234565.
 ¹    # Push input again.
  Ù   # Uniquify the input. E.g. 111223345565 would give 123456.
   Q  # Check if equal, which yields 1 or 0.

Uses CP-1252 encoding.

Try it online!

R, 66 48 46 43 bytes

function(s)identical(x<-rle(s)$v,unique(x))

This is a function that accepts the input as a vector of digits and returns a boolean. To call it, assign it to a variable.

It certainly isn't the shortest but I thought it was a fun approach. We run length encode the input and extract the values. If the list of values is identical to itself with duplicates removed, return TRUE, otherwise FALSE.

Verify all test cases online

Saved 20 bytes thanks to MickyT and 3 thanks to Albert Masclans!

MATL, 8 bytes

t!=tXSP=

The output is an array containing only ones for truthy, or an array containing at least one zero for falsey.

Try it online!

Explanation

Consider the input 22331, which satisfies the condition. Testing if each character equals each other gives the 2D array

1 1 0 0 0
1 1 0 0 0
0 0 1 1 0
0 0 1 1 0
0 0 0 0 1

The final result should be truthy if the rows of that array (considered as atomic) are in (lexicographical) decreasing order. For comparison, input 22321 gives the array

1 1 0 1 0
1 1 0 1 0
0 0 1 0 0
1 1 0 1 0
0 0 0 0 1

in which the rows are not sorted.

t!   % Take string input. Duplicate and tranpose
=    % Test for equality, element-wise with broadcast: gives a 2D array that
     % contains 0 or 1, for all pairs of characters in the input
t    % Duplicate
XS   % Sort rows (as atomic) in increasing order
P    % Flip vertically to obtain decreasing order
=    % Test for equality, element-wise

Pyth, 7 bytes

{IeMrz8

Test Suite.

Ruby, 23 bytes

Anonymous function. Accepts a string. Regex strat.

->n{/(.)(?!\1).*\1/!~n}

Regex breakdown

/(.)(?!\1).*\1/
 (.)            # Match a character and save it to group 1
    (?!\1)      # Negative lookahead, match if next character isn't
                #  the same character from group 1
          .*    # Any number of matches
            \1  # The same sequence as group 1

!~ means if there are no matches of the regex within the string, return true, and otherwise return false.

Mathematica, 26 bytes

0<##&@@Sort[#&@@@Split@#]&

Python, 56 bytes

a=lambda s:1-(s[0]in s.lstrip(s[0]))&a(s[1:])if s else 1

Haskell, 44 bytes

import Data.List 
((==)<*>nub).map head.group

Usage example: ((==)<*>nub).map head.group $ "44999911" -> True.

A non-pointfree version:

f x = q == nub q                -- True if q equals q with duplicates removed
  where
  q = map head $ group x        -- group identical digits and take the first
                                -- e.g. "44999911" -> ["44","9999","11"] -> "491"
                                -- e.g  "3443311" -> ["3","44","33","11"] -> "3431"

Retina, 17 bytes

M`(.)(?!\1).+\1
0

Try it online! (Slightly modified to run all test cases at once.)

The first regex matches digits which are separated by other digits, so we get a 0 for valid inputs and anywhere between 1 and 9 for invalid inputs (due to the greediness of the the .+, we can't get more than n-1 matches for n different digits).

To invert the truthiness of the result, we count the number of 0s, which is 1 for valid inputs and 0 for invalid ones.

MATL, 13 11 bytes

u"G@=fd2<vA

Thanks to Luis Mendo for saving two bytes!

Try it Online!

Explanation

        % Grab the input implicitly
u       % Find the unique characters
"       % For each of the unique characters
    G   % Grab the input again
    @=  % Determine which chars equal the current char
    f   % Find the locations of these characters
    d   % Compute the difference between the locations
    2<  % Find all index differences < 2 (indicating consecutive chars)
    v   % Vertically concatenate all stack contents
    A   % Ensure that they are all true
        % Implicit end of the for loop

Julia, 35 bytes

s->issorted(s,by=x->findfirst(s,x))

For whatever reason, sort does not take a string, but issorted does...

Java, 161 bytes

Because Java...

Shamelessly stealing borrowing the regex from this answer because I started out trying to do this with arrays and math manipulation, but it got hideously complex, and regex is as good a tool as any for this problem.

import java.util.regex.Pattern;public class a{public static void main(String[] a){System.out.println(!Pattern.compile("(.)(?!\\1).*\\1").matcher(a[0]).find());}}

Ungolfed:

import java.util.regex.Pattern;

public class a {
    public static void main(String[] args) {
        System.out.println(!Pattern.compile("(.)(?!\\1).*\\1").matcher(args[0]).find());
    }

Laid out like a sensible Java person:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class  {
    public static void main(String[] args) {
        Pattern p = Pattern.compile("(.)(?!\\1).*\\1");
        Matcher m = p.matcher(args[0]);
        System.out.println(!m.find());
    }
}

JavaScript ES6, 71 69 bytes

h=y=>y.match(/(.)\1*/g);x=>h((u=h(x)).sort().join``).length==u.length

Or, equivalently:

x=>((u=x.match(r=/(.)\1*/g)).sort().join``).match(r).length==u.length
x=>(h=y=>y.match(/(.)\1*/g))((u=h(x)).sort().join``).length==u.length

Golfing in progress.

Verify test cases

var truthy = `3
51
44999911
123456789
222222222222222222222`.split `
`;
var falsey = `818
8884443334
4545
554553
1234567891`.split `
`;

var Q = x => ((u = x.match(r = /(.)\1*/g)).sort().join ``).match(r).length == u.length;
truthy.concat(falsey).forEach(e => {
  t = document.createTextNode(`${e} => ${Q(e)}`);
  o.appendChild(t);
  o.appendChild(document.createElement("br"));
});

* {
  font-family: Consolas, monospace;
}

<div id=o></div>

Lua, 107 Bytes

At least, it beats Java :D. Lua sucks at manipulating strings, but I think it is good enough :).

It takes its input as a command-line argument, and outputs 1 for truthy cases and false for falsy ones.

(...):gsub("(.)(.+)%1",function(...)a,b=...if b:find("[^"..a.."]")then print(1<0)os.exit()end end)print(1)

Ungolfed

Be care, there's two magic-variables called ..., the first one contains the argument of the program, the second one is local to the anonymous function and contains its parameters

(...):gsub("(.)(.+)%1",  -- iterate over each group of the form x.*x and apply an anonymous
  function(...)          -- function that takes the captured group as parameters
  a,b=...                -- unpack the values in the locale ...
  if b:find("[^"..a.."]")-- if the captured group (.+) contain other character than
  then                   -- the one captured by (.)
    print(1<0)           -- ouput false
    os.exit()            -- and exit
  end
end)
print(1)                 -- output 1, reached only when the string is okay :)

R 33 bytes Not working

Trying to reduce the bytes of Alex A.,

all({x=rle(scan())$v}==unique(x))

Perl 5, 20 bytes

A subroutine:

pop!~/(.)(?!\1).+\1/

See it in action as:

perl -e'print sub{pop!~/(.)(?!\1).+\1/}->(51)'

Factor, 22 bytes

[ dup natural-sort = ]

Does what it says on the tin. As an anonymouse function, you should call this, or make it a : word ;.

J, 8 bytes

-:]/:i.~

Test it with J.js.

How it works

-:]/:i.~  Monadic verb. Argument: y (list of digits)

     i.~  Find the index in y of each d in y.
  ]/:     Sort y by the indices.
-:        Match; compare the reordering with the original y.